127 votes
Accepted

Why is it best to use a prime number as a mod in a hashing function?

Consider the set of keys $K=\{0,1,...,100\}$ and a hash table where the number of buckets is $m=12$. Since $3$ is a factor of $12$, the keys that are multiples of $3$ will be hashed to buckets that ...
Mario Cervera's user avatar
24 votes

Can any known sub-Turing-complete model of computation enumerate precisely the set of prime numbers?

There is an important class of primitive recursive functions. Citing Wikipedia, [P]rimitive recursive function is roughly speaking a function that can be computed by a computer program whose loops ...
Ivan Smirnov's user avatar
12 votes
Accepted

What is the time complexity of checking if a number is prime?

When $n$ is the input, we test $\sqrt{n}$ divisors. However, we also have to take into account the complexity of division itself. For a number with $b$ bits, this takes $O(b \log b \log\log b)$ ...
wythagoras's user avatar
12 votes
Accepted

Primality testing: Why is dividing a number $n$ by every integer between 2 and $\sqrt{n}$ an inefficient test?

The complexity is measured as a function of the size of the input. You don't have here an array of $n$ numbers but a number $n$. The size of the input is $O(\log n)$ (to store a number $n$ you need $\...
abc's user avatar
  • 1,625
10 votes

More details about the Baillie–PSW test

The advantage in using base 2 is that we know all of the psp's base 2 up to $2^{64}$. It has been verified that none of these psp(2)'s passes a Lucas test when the parameters $P, Q$ are chosen in ...
Robert Baillie's user avatar
9 votes
Accepted

Algorithm for checking if a list of integers is pairwise coprime

First, two facts about coprime integers: Iff $a$ and $b$ are coprime, then $ab = \mathrm{lcm}(a,b)$ Iff $a$ is coprime to both $b$ and $c$, then $a$ is coprime to $bc$ It follows from this that a ...
Draconis's user avatar
  • 7,138
8 votes

Can any known sub-Turing-complete model of computation enumerate precisely the set of prime numbers?

The primes can be recognized in linear space by a Turing machine. Linear space-bounded Turing machines are not universal. So, I think I have to disappoint you.
Hendrik Jan's user avatar
  • 30.6k
7 votes

Sieve of Eratosthenes vs. Sieve of Sundaram

Although this question is old, the considerations are still relevant and there is still some lack of proper analysis on which prime sieve to choose for various purposes. In this evaluation, it is ...
GordonBGood's user avatar
7 votes

Primality testing: Why is dividing a number $n$ by every integer between 2 and $\sqrt{n}$ an inefficient test?

newbie's answer already explains it all. But if I had to add something to this, I'd put it in simpler words. When you talk about a polynomial time algorithm, what you actually mean is that the ...
mursalin's user avatar
  • 413
7 votes

Can any known sub-Turing-complete model of computation enumerate precisely the set of prime numbers?

Belated citation add: see Fischer or Gordon for more on essentially this line of thought. As observed above, "locally" the problem of enumerating primes is very easy: the function sending $...
Noah Schweber's user avatar
6 votes
Accepted

Complexity of finding factors of a number

When you assume that arithmetic operations can be done in time $O(1)$, you're assuming that the numbers you're dealing with have a constant maximum number of digits. That's not a reasonable ...
David Richerby's user avatar
6 votes

Can any known sub-Turing-complete model of computation enumerate precisely the set of prime numbers?

Yes. Friant [1] proved that the language $\{ a^p \mid p \text{ is prime}\}$ is a context-sensitive language, which is far stronger than recursively enumerable. My grandfather Benny Brodda [2] then ...
Carl-Fredrik Nyberg Brodda's user avatar
6 votes
Accepted

Is Determining the Number of distinct Prime Factors Polynomial?

No problem involving factorization is known to be polynomial time, and these problems (formulated as decision problems in any reasonable way) are suspected to be NP-intermediate. The only problem ...
Yuval Filmus's user avatar
5 votes
Accepted

Given a prime power, is it possible to efficiently compute the prime

Yes, here is a simple approach (there are likely more efficient ones). Let $n$ be the number given. Observe that $2 \leq p \leq n$ and $1 \leq i \leq \log_2(n)$. For each possible value of $i$ in the ...
Pontus's user avatar
  • 687
5 votes

Complexity of finding factors of a number

The exact running time depends on your computation model. When analyzing arithmetic with large numbers, we usually count either bit operations, or arithmetic operations on words of size $O(\log n)$ (...
Yuval Filmus's user avatar
5 votes

More details about the Baillie–PSW test

References for the test: Pomerance, Selfridge, Wagstaff, "The Pseudoprimes to 25 x 10^9", July 1980. Page 1024-1025, Check if n is a strong probable prime base 2. Check whether n is a Lucas probable ...
DanaJ's user avatar
  • 604
5 votes

Why is it best to use a prime number as a mod in a hashing function?

First of all, the question is phrased incorrectly. The following are equivalent and correct expressions of the intended question: why must we use a prime number as the modulo of the hash value (not "...
bking's user avatar
  • 51
5 votes
Accepted

How to compute all primes between upto $n$ in time $O(n)$ time?

You can use a sieve to enumerate all prime numbers up to $n$. There are multiple algorithms; see the Wikipedia article I link for some examples. The sieve of Atkin and wheel sieves apparently run in ...
D.W.'s user avatar
  • 159k
5 votes

Algorithm for checking if a list of integers is pairwise coprime

Yes. The naive approach of checking each pair of numbers takes quadratic time, but there are more efficient algorithms. There is a nearly-linear time algorithm, described in the following paper: ...
D.W.'s user avatar
  • 159k
4 votes
Accepted

How to compute Jacobi symbol efficiently?

The Wikipedia article on the Jacobi symbol describes an efficient algorithm for calculating it which uses quadratic reciprocity and operates similarly to the GCD algorithm.
Yuval Filmus's user avatar
4 votes

Is finding all primes less than n, doable in polynomial time?

No, it doesn't. There are exponentially many primes less than $n$, so you can't enumerate them in polynomial time.
D.W.'s user avatar
  • 159k
4 votes
Accepted

Why is the complexity of factorial a function of n?

Complexity can be expressed in terms of any reasonable measure. For example, when discussing graph algorithms, we usually state the complexity in terms of the number of vertices and/or edges, rather ...
David Richerby's user avatar
4 votes
Accepted

Logarithmic run time for calculating prime numbers?

Let's use a different parameter for your input, $m$. The number of instructions that your algorithm executes in the worst case is $O(m)$. We often measure the running time of algorithms in terms of ...
Yuval Filmus's user avatar
4 votes

How much time (in hours) will it take to check if the number with 20 binary digits is the prime number?

Primality testing is very fast with the Miller–Rabin algorithm [1]. You can use the deterministic variant with witnesses 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, and 37 to test any 64 bit number in $O(\...
Laakeri's user avatar
  • 1,339
4 votes

While number can be checked for primality in O(n^0.5) then why was it considered to be not in P until AKS test?

The bit length of $n$ is $\log(n)$, if we forget about the most significant digits, which is always $1$ except for $n=0$. As a function of $t=\log(n)$ you have $n^{1/2}=2^{t/2}$. It is in terms of the ...
plop's user avatar
  • 1,189
4 votes
Accepted

Prime factorization for compressing streams of random numbers

No. If it is a stream of random bytes, where each byte is independently and uniformly distributed, it cannot be compressed. It doesn't matter what method you're using. You're trying to do something ...
D.W.'s user avatar
  • 159k
4 votes
Accepted

Fast identification of prime power factors?

In the worst case, this is probably about as hard as factoring. As far as we know, factoring squarefree integers is about as hard as factoring integers in general, so for the case $e=1$, this is ...
D.W.'s user avatar
  • 159k
4 votes

What is the time complexity of this algorithm of finding all prime numbers?

The following complexity is not tight; however closeby: The complexity of the algorithm is at least $\Omega(n \sqrt{n}/\log^2 n)$ and at most $O(n \sqrt{n}/\log n)$. For any natural number $x$, the ...
Inuyasha Yagami's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible