Home Prime I.T.

Note : This article has been translated using an automatic translator and one pass was made to remove biggest errors.
If you want to contribute to the readability of this article, you can notify me translations errors (a word, a sentence, a paragraph) by contacting me at the email address at the bottom of the page. Thanks

Primes numbers

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 the bank).

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 :

MAX	Pi
10	4 The four prime numbers less than 10 are: 2, 3, 5, 7
100	25
1 000	168
10 000	1 229
100 000	9 592
1 000 000	78 498
10 000 000	664 579
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.

By sieving

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 considerations.
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".

The site

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... :)