In order to know at once a large number of consecutive and not too great numbers (for example less than one billion), we have a method that is more than 2,000 years old: Sieve of Eratosthenes
Eratosthenes teaching at Alexandria. ©
The sieve of Eratosthenes consists writing all the numbers of a given interval, then methodically eliminating the multiples of the successive prime numbers already known, stopping at the square root of the upper bound of the interval. The remaining numbers are the prime numbers of the interval. This is a good method, often used to constitute successive primes lists, or between 2 and n (usual case) or even between any two terminals A and B .
Erratosthene Sieve Algorithm :
To know all prime numbers up to n :
- Write all integers from 2 to n ;
- Remove all multiples of 2 except 2;
- Identify the first number greater than 2 still present, that is, 3, and remove all multiples of 3 except 3;
- Identify the first number greater than 3 still present, that is, 5, and remove all multiples of 5 except 5;
- etc.
- Stop as soon as you have reached the square root of n ;
- What remains is the table of prime numbers up to n .
The limits of this method are again fixed by the memory space available and which prevents us from considering sets of numbers that are too large. The Sieve has recently been used to accurately count the twin prime numbers (to separated from two units, such as 11 and 13) less than 10^15, as well as to study the discrepancies between prime numbers. On this occasion, the Sieve was applied in 10^ 10 parties : after saving the desired information, the results of the calculation of each 100,000 slices (except the first) were erased in order to process the next one.
The Sieve of Eratosthenes applied to the first 400 integers, arranged in a block of 20 x 20 (left). Even numbers ending with an even number, all even-numbered columns are empty (except the first, which contains 2). There are also "gaps" of three columns: they correspond to the elimination of the multiples of five which end in five, flanked by two columns of even numbers, empty also. The multiples of two and five, characterized by their last figure, are the only ones to be divided into columns. The rest of the pattern looks disorderly. On the right, the sieve of Erastosthenes applied to the first 10,000 integers, arranged in a block of 100 x 100. We find the alternation of one column out of two, corresponding to the even numbers, And the gaps of three columns empty of ten in ten. ©
If, instead of erasing them, the intermediate results had been saved each time, we would have had the table of 29,844,570,422,669 prime numbers less than 10^15 . The storage of this table would require a 20.10 memory 12 bytes , more than 30,000 CD-ROM of 650 megabytes each, or more than 1,000 DVD Dual front layer 17 GB each (these are the DVD higher capacity today ). It is clear that to know prime numbers of 20 digits or more or to factorize integers of this size, the Eratosthenes screen is not suitable. In 100 years, if technical progress continues to speed Of doubling every 18 months, we will go at best to 10^40 with the screen.
Example of Erathosthenes sieve for prime numbers less than 100. It is not necessary to examine multiples beyond those of seven. ©
Constituting very large tables of prime numbers is impossible - because of the necessary memory - and unnecessary, because other methods are available to know the primality: it is better to recalculate than to store. Today, it is known to test if any integer number of 100 digits is prime, whereas a computer of the size of the Solar System wouldn't be enough to store the table of all the prime numbers less than 10^100 .
Spiral of Ulam for the integers from 1 to 10.000 (on the left). Ulam spiral for integers from 1 to 100,000 (right). ©
The representations of the Sieve also give rise to the question of the distribution of prime numbers. In the process of eliminating the multiples of the successive prime numbers, regular cuts are made in the mass of integers. For example, when the integers of a block interval are arranged, the elimination of even numbers causes empty columns to appear in pairs, and in general the elimination of the multiples of the first p- number empties the spaces Of p in p
Assistant to a boring conference at a congress in 1963, mathematician Stanislaw Ulam scribbled a spiral of integers by blackening prime numbers. To his surprise, he saw many oblique alignments appear. These alignments correspond to formulas of the type an^ 2 + bn + c, which, although it isn't clear, sometimes generate a large proportion of prime numbers. For example, the Euler formula, f ( n ) = n^2 - n + 41, gives prime numbers for all values of n between o and 40. ©
However, the combination of these regular sections reveals a pattern without obvious regularity, apart from the empty columns of even numbers and the numbers of the numbers ending in five.
Ulam spirals of all sizes can be drawn, for example from 1 to 1,000. They can also be centered on a number other than 1. ©
Another representation of prime numbers, however, reveals additional structures: it is the Ulam spiral, discovered by the mathematician Stanislaw Ulam. It consists in arranging the successive integers, generally from 1, into a spiral growing towards the outside, where the prime numbers are emphasized. Diagonal lines rich in prime numbers, still poorly understood, then appear.