Take the 2-minute tour ×


And is there any algorithm which generates all prime numbers p?

share|improve this question

2 Answers 2

up vote 5 down vote accepted

The prime number theorem states that $\pi(x)$, or the number of primes less than or equal to $x$ obeys the following property:

$$\lim_{x\rightarrow \infty} \frac{\pi(x)}{x/\ln x} = 1 $$

Meaning that we can approximate the number of primes less than $x$ by $x/\ln x$.

Numbers representable by $n$ bits are those less than $2^n$. Therefore, with $1024$ bits, you can count up to $2^{1024}$, which is an enormous number. I believe you want to know about the prime numbers which are representable by $1024$ bits and by no fewer than that amount. We can approximate this by:

$$\pi(2^{1024})-\pi(2^{1023}) \approx \frac{2^{1024}}{\ln 2^{1024}} - \frac{2^{1023}}{\ln 2^{1023}} \approx 1.26\cdot 10^{305}$$

according to Wolfram Alpha.

To answer your second question: yes. There is a very well known algorithm to generate all prime numbers called the Sieve of Eratosthenes. The algorithm seeks to identify prime numbers by process of elimination. To begin the algorithm, make an arbitrarily long list of numbers you would like to test for primality. For example, let's test the first 20 numbers. First, we can exclude 1 because it is defined to be composite:

$$\{ 2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20\}$$

We identify $2$ as our next prime, because it can have no factors besides one and itself. We then remove all subsequent multiples of 2 because they have at least one factor, and we're left with:

$$\{ 2,3,5,7,9,11,13,15,17,19\}$$

Next, $3$ must be prime because it hasn't been eliminated as a multiple of 2. Any subsequent multiple of $3$ will not be prime, so we eliminate them:

$$\{ 2,3,5,7,11,13,17,19\}$$

$5$ is next on our list, and must be prime because it hasn't been crossed out as a multiple of 2 or 3. We eliminate all subsequent multiples of $5$ from our list. There aren't any left less than 20! Indeed because $5^2 > 20$, we can be sure that we have eliminated all composite numbers from our list. Conceivably, we could perform this algorithm on any length of list, as long as we are careful to keep track of which numbers have been eliminated.

share|improve this answer
Really nice answer! Just a minor oversight: 10 is still a multiple of 5 which is below 20. –  Paresh Dec 22 '12 at 9:26
Thanks for catching that! 10 is definitely not prime. –  orlandpm Dec 22 '12 at 10:08

Not - your request is too large for an exact result or for a complete list.

$2^{1024}$ is almost $1.8 \times 10^{308}$ which is much much larger than the number of particles in the universe. So forget the list.

There are ways of counting the number of primes up to a given number which do not rely of finding them all. This is the prime counting function $\pi(x)$ and the record seems to be of the order of $$\pi(10^{24}) = 18,435,599,767,349,200,867,866$$ implying that almost $1$ in $54$ of the numbers up to $10^{24}$ are prime.

Using reasonable approximations based on the prime number theorem, almost $1$ in $700$ of the numbers up to $2^{1024}$ are prime.

share|improve this answer

Your Answer


