sieves

sieves

sieves

We saw last week that Chinese mathematician Chen Jingrun proved the theorem that bears his name using riddle theory, a powerful method dating back at least to the third century BC. c.

In fact, the most famous of the numerical sieves is that of Eratosthenes (276-194 BC), a simple algorithm (of the “old woman” type) for finding prime numbers less than a certain natural number n. Write the numbers between 2 and n, crossing out those that are not prime in successive steps: start with 2 and cross out all its multiples (i.e. all even numbers); We go back to the top of the list and the first number not crossed out, 3, is a prime number, and we continue to cross out all its multiples, and so on. The process ends when the square of the last prime number found is greater than n.

More information

For example, let’s look for the prime numbers less than 20. We list the numbers from 2 to 20 and mark the multiples of 2:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

The first unmarked number is 3, so its multiples are marked:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

The next unmarked number is 5, and since its square is greater than 20, the process is over and the primes are the unmarked numbers:

2 3 5 7 11 13 17 19

The process, which is a bit cumbersome with a long list of numbers, can be simplified (in what way?).

As an anecdote (and information of interest to programmers), the computer version of Eratosthenes’ sieve has become a standard way of comparing the efficiency of different programming languages.

More than his sieve, Eratosthenes is famous for his remarkably accurate calculation of the diameter of the earth, for making geography and geodesy disciplines with their own entity and method, and for introducing procedures and terminologies that are still used today. But that’s another article.

Other screens

After Eratosthenes, other sieves (too advanced to be discussed here, although their mathematical basis is relatively simple), such as Eulers, Legendres, Bruns, Selbergs, or the so-called “great sieve”, have achieved some partial success in the hopeless task of finding themselves to deal with Goldbach’s conjecture. Like the Bombieri-Friedlander-Iwaniec theorem, which shows that there are infinitely many primes of the form a² + b⁴, where a and b are integers and not necessarily distinct (I dare the perceptive reader to list the first primes of this kind and draw a conclusion). And Chen Jingrun, who, as we have seen, has shown that any large enough even number is the sum of two primes, or one prime and one semiprime. In turn, he proved that there are infinitely many primes p such that p+2 is a prime or semiprime, an important step in proving the twin prime conjecture that there are infinitely many pairs of twin primes.

In the mid-19th century, the French mathematician Alphonse de Polignac made a more general conjecture that for every natural number n there are infinitely many pairs of primes whose difference is 2n. In the case of n = 1 we have the twin prime conjecture. Can you find some prime number pairs for n = 2, 3, 4…?

you can follow OBJECT on Facebook, Twitter and Instagram, or sign up here to receive our weekly newsletter.