A prime number is a natural number which has no divisors other then 1 and itself.
With this mathematical property, these numbers are the basis of modern
cryptography and are often used in computer science to make our messages
unreadable for outsiders and thus keep confidential all "our little secret"
that passes from hand to hand (for example sending the password to our
favorite social network or the payment order between the merchant and
But how to find all primes between 1 and N ?
One of the great mathematical and algorithmic game is to find the
maximum of these numbers. Some do it for "the beauty of the game and the
spirit", others to study because there are still many questions
about these numbers. This is even more important because we must ensure
that cryptography based on prime numbers is not breakable and that
we will not find "our little secret" in nature.
It should be noted that there is an infinity of primes, below the number
of prime numbers (Pi) up to 1 billion to give an idea :
The four prime numbers less than 10 are: 2, 3, 5, 7
1 000 000
10 000 000
100 000 000
5 761 455
1 000 000 000
50 847 534
There are 50 million primes with 9 digits (in base 10)
By primality test
There are several methods to calculate a range of prime numbers
between 1 and N. A relatively naive, is to go through all the numbers one
by one and test each of them if it is prime or not by using an algorithm
named "primality test".
The best known of these tests is the "trial division" which trying to
divide the selected number by all the numbers less than its square root.
If no divisor is found then this number is prime. (note : do you see why
"less than its square root ?" You have to find...). This algorithm is part of
the family of deterministic primality tests that can tell for sure if the number
is prime or not when the algorithm is finished.
This family is to be contrasted with probabilistic primality tests that indicates
whether the number to test "have high chance" of being prime or not, one of
the most used is the Miller-Rabin algorithm.
In terms of efficiency, probabilistic algorithms are faster but they offer
an idea of the primality of numbers and not what it really is. Finally all these
algorithms are not "so fast" because they are used to determine the primality in
a timely manner (I choose this number is it prime or not ?) but are not very
effective when we want calculate a range of prime number.
Obviously it is possible to mix the two families to try to improve performance,
but there is much more effective, it is sieve algorithms.
The purpose of these algorithms is to apply a sieve to the numbers, ie
discriminating the numbers from their properties, their positions or relationships
and so develop an algorithm "strainer" that will pass the numbers not prime
(composites) and thus keep the primes.
The best known is the Sieve of Eratosthenes, it is not only fast but also it is
easy to understand because it does not fit into difficult mathematical
There are other sieves for example sieve of Atkin that is considered as an improved
version of Eratosthenes. This algorithm has been developed recently (from 2000),
but its mathematical concepts start to become difficult and very few extension
information circulating over.
In terms of efficiency, sieve algorithms are more effective by cons they have
weak point (it must be one ...) : they are greedy in memory because for the launch
of the sieve the program must collect all numbers in the range 1..N in memory
before launching the "sieve".
On this site you will find :
An online version (php) of the sieve of Eratosthenes to compute primes
ranges up to 1000 billion (12 digit number).
An explanation of the Sieve of Eratosthenes and several java
implementations of the algorithm (standard and optimized) for finding all
prime numbers up to 100 billion.
Finally some implementations and tracks on Atkin.
Attention to the optical illusion between the php online version and
the java versions of Eratosthenes. The online version seems to give 10 times
more number than the java version but in in fact it is less powerful...
Because it gives ranges of 600 primes at best while the java version gives
all (1 up to N).
For something equivalent, it would click about 1 billion times the button
"next" in online version for all prime numbers up to 1000 billion
It would take 16 years if we consider that the display time between
two webpages is 0.5 sec... :)