Articles

The distribution of prime numbers and Eratosthenes sieve


We know that there is an infinite number of prime numbers and that every nonzero integer expresses itself as a product of prime numbers. The number 12 expresses itself as 22.3, the product of cousins ​​2, 2 and 3. How can we tell if a number is prime? Is there an algorithm, that is, a process with a finite number of steps to decide if a number is prime or compound like 12?

This question was already in the minds of the Greek mathematicians of classical antiquity and the answer is positive. If we want to know if the positive integer no > 1 is prime, just make sure no is divisible by integers m smaller than no. However, this idea can be refined because it is shown that it is sufficient to verify the divisibility of no cousins ​​less than or equal to Ön. That is, we affirm that if no is is not a prime number so there is a prime P such that P divide no and P <= Ön. In fact, as we are assuming that no it's not a prime number, no is then a compound number and therefore can be decomposed as no = ab. If The > Öno and B > Öno, then no = ab > (Öno) (Öno) = no, a contradiction. So we have The <= Öno and B <= Öno, and every cousin P that divides The satisfy P <= The <= Öno. So the prime integers xsuch that x <= Öno, are the only ones we need to test to find the dividers of no. That is, just divide no by 2, 3, 5,…, until we find the largest integer smaller than Öno.

For example, we would like to know if the number 107 is prime. The square root of 107 is between 10 and 11, that is, 10 <Ö107 <11. So we test whether 107 is divisible by 2, 3, 5, 7. But 107 is not divisible by these cousins. We conclude that the number 107 is prime. On the other hand, the same process allows us to determine the prime factors of a compound number. As another example, if no = 319, so its square root Ö319 is between 17 and 18 and therefore we test its divisibility by cousins ​​less than or equal to 17. We find that 319 = 11.29, ie 319 is the product of 11 by 29. To break down 29 into prime factors, we tested their divisibility by primes less than or equal to 5, because the square root of 29 is between 5 and 6. Since 29 is not divisible by 2, 3, and 5, we conclude that 29 is prime and therefore 319 = 11.29 is the decomposition of 319 into prime factors.

Note that this algorithm is based on division, and although the algorithm works, if we consider high numbers we will have to undertake a huge number of divisions, which would be time consuming. The mathematician Eratosthenes of Cyrene, a contemporary of Archimedes and Aristarchus, author of the most celebrated antiquity for the radius of the earth, developed a systematic method for obtaining cousins ​​smaller than a given number, using multiplication rather than division operation, which makes the algorithm easier to implement. This algorithm is known as the Eratosthenes sieve, or sieve method. Eratosthenes was born in 276 BC, died in 196 BC, studied philosophy in Athens, and was director of the famous library of Alexandria, and an eminent mathematician, geographer, historian, philologist, and poet. Eratosthenes' sieve determines all prime numbers less than a certain number x given away. Therefore, it determines the prime factors of compound numbers less than x.

Note that every compound number no has a divisor less than or equal to its square root Öno. This suggests a procedure for building a list of all prime numbers that do not exceed an integer. xif cousins ​​smaller than Öx are already known. Consider the integers from 2 to x, listed in ascending order. Let's keep the cousins ​​from 2, 3, 5,…, until Öx, and discard all their multiples.

In general, how do we remove multiples from some cousin Pr of this list, the first remaining integer greater than Pr, is also a prime number, say Pr +1. In fact, otherwise it would be divisible by some smaller cousin (actually smaller than its square root) and would have already been removed. Also note that we need not worry about integers smaller than (Pr +1)2because compound numbers less than (Pr +1)2 have already been removed because they all had a prime factor less than Pr +1. Therefore, it is sufficient to begin each step by removing the multiples of Pr +1 and discarding (Pr + 1)2.

As an example, let's determine all prime numbers less than 23 using the sieve method. In the list below, the representation of the number in bold means that it was dropped in one step of the algorithm. For example, 6 is discarded because it is a multiple of prime 2.

We have: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23. Therefore 2, 3, 5, 7, 11, 13, 17,19 are prime integers less than 23.

The sieve method is efficient for obtaining a list of cousins ​​smaller than a not too large integer, and since Eratosthenes's time the method has been used to estimate the number of cousins ​​in a range. However, if we try to get a list of integers that have been discarded, we get a formula for the exact or approximate number of primes P x, we will have serious difficulties. The sieve method has undergone a number of refinements over time. Mathematicians Brun, Rademacher, Meissel, and especially Selberg, generalized the Sieve method and thus many classical problems of Number Theory were successfully re-studied.

Two prime numbers say twin cousins ​​if the difference between them is 2. Some examples of twin prime pairs are: 3 and 5, 5 and 7, 11 and 13, 17 and 29, 29 and 31, 41 and 43. Scholars of Number Theory conjecture but cannot demonstrate that there are infinite twin cousins. Norwegian mathematician Brun, in 1919, developed the double sieve method and made some estimates of the number of twin cousins.

In 1950 Norwegian mathematician A. Selberg won the Fields Medal (the highest distinction for a mathematician) for developing an extraordinarily efficient method of estimating the distribution of prime numbers. This award represents a milestone, as it was the first time a mathematician had won a Fields Medal for a work on Number Theory. Selberg obtained much more accurate estimates using his refinement of the sieve method and thus solved many classical problems in Number Theory. Selberg gave an elementary demonstration of the asymptotic law of prime number distribution, that is, the prime number theorem. The mathematicians Hadamard and de la Vallée-Poussin gave, in 1897, the first demonstration of this theorem using mathematical analysis, more precisely, Theory of Complex Functions. The Prime Number Theorem evaluates how often prime numbers occur, in other words, the rate of growth of prime numbers in the sequence of positive integers. Thanks to Atle Selberg and Paul Erdös it was possible to obtain a demonstration of the Prime Number Theorem, completely based on estimates, without the use of Complex Analysis. Selberg's investigations into Analytical Number Theory facilitated advances in a series of thorny problems and revealed unusual links between Number Theory and other areas of mathematics. For example: discrete group theory and automorphic forms, semi-simple Lie group representations, Riemann's Zeta function theory, and many others.

Back to columns

<