# Tag Info

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 ...
• 3,744

### 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 ...
• 944
Accepted

• 2,960

### 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 ...
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 ...
• 278k

### 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 "...
• 51
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 ...
• 687
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 ...
• 163k

### 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 ...
• 614

### 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: ...
• 163k

### 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.
• 163k
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 ...
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 ...
• 278k