# Questions tagged [primes]

The tag has no usage guidance.

86 questions
Filter by
Sorted by
Tagged with
57k views

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

If I have a list of key values from 1 to 100 and I want to organize them in an array of 11 buckets, I've been taught to form a mod function $$H = k \bmod \ 11$$ Now all the values will be placed ...
9k views

### When is the AKS primality test actually faster than other tests?

I am trying to get an idea of how the AKS primality test should be interpreted as I learn about it, e.g. a corollary for proving that PRIMES ⊆ P, or an actually practical algorithm for primality ...
6k views

### Data compression using prime numbers

I have recently stumbled upon the following interesting article which claims to efficiently compress random data sets by always more than 50%, regardless of the type and format of the data. Basically ...
1k views

### Why is factoring large integers considered difficult?

I read somewhere that the most efficient algorithm found can compute the factors in $O(\exp((64/9 \cdot b)^{1/3} \cdot (\log b)^{2/3})$ time, but the code I wrote is $O(n)$ or possibly $O(n \log n)$ ...
1k views

### Is determining if there is a prime in an interval known to be in P or NP-complete?

I saw from this post on stackoverflow that there are some relatively fast algorithms for sieving an interval of numbers to see if there is a prime in that interval. However, does this mean that the ...
220 views

### Complexity-theoretic difficult of checking the value of $\pi(x)$?

The prime-counting function, demoted $\pi(x)$, is defined as the number of prime numbers less than or equal to $x$. We can define a decision problem from $\pi(x)$ as follows: Given two numbers $x$ ...
5k views

### Why Miller–Rabin instead of Fermat primality test?

From the proof of Miller-Rabin, if a number passes the Fermat primality test, it must also pass the Miller-Rabin test with the same base $a$ (a variable in the proof). And the computation complexity ...
581 views

### Efficiently computing the smallest integer with n divisors

In order to tackle this problem I first observed that $$\phi(p_1^{e_1} \space p_2^{e_2} \cdots \space p_k^{e_k}) = (e_1 + 1)(e_2 + 1)\cdots(e_k +1)$$ Where $\phi(m)$ is the number of (not ...
610 views

### More details about the Baillie–PSW test

It's clear that Mathematica uses the Baillie–PSW test for its PrimeQ function (which tests primality), and as I read in the Mathematica documentation, it starts with trial division, then base 2 ...
4k views

### Algorithm for checking if a list of integers is pairwise coprime

Are thre any efficient algorithms for checking if a list of integers is pairwise coprime, or would a more general algorithm be the best option available?
1k views

### What is the average-case complexity of trial division?

The trial division algorithm for checking if a number $N$ is prime works by trying to divide $N$ by all integers in the range 2, 3, ..., $\lfloor \sqrt{n} \rfloor$. If any of them cleanly divide $N$, ...
1k views

### What is the name of this prime number algorithm?

Does the following recursive algorithm have a name? If so, what is it? ...
Could some one please explain how to get the time complexity of checking if a number is prime? I'm really confused as to if it is $O(\sqrt{n})$ or $O(n^2)$. I iterate from $i=2$ to $\sqrt{n}$ and ...