New Take on an Ancient Method Improves Way to Find Prime Numbers

From Scientific American:

But Helfgott, 38, went even farther back in time and conceived an improved version of the sieve of Eratosthenes, a popular method for finding prime numbers that was formulated circa 240 B.C. Helfgott’s proposed version would reduce the requirement of physical space in computer memory, which in turn would reduce the execution time of programs designed to make that calculation.

Prime numbers are something like “atoms of mathematics,” which can only be divided by themselves and the number 1. Eratosthenes of Cyrene—a Greek mathematician, astronomer and geographer who was director of the Library of Alexandria and became famous for calculating the circumference of Earth—also proposed a practical method to identify them: the “sieve,” or filter. “Like many other children, I was taught this it in primary school when I was 10, with a table,” says Helfgott, who is currently a researcher at the National Center for Scientific Research (CNRS) and the University of Göttingen.

In order to determine with this sieve all primes between 1 and 100, for example, one has to write down the list of numbers in numerical order and start crossing them out in a certain order: first, the multiples of 2 (except the 2); then, the multiples of 3, except the 3; and so on, starting by the next number that had not been crossed out. The numbers that survive this procedure will be the primes. The method can be formulated as an algorithm and computers can quickly run it.

While working on correcting tests for a book with the full demonstration of Goldbach’s weak conjecture, Helfgott says he began thinking—“maybe for too much time”—about the problem of the sieve of Eratosthenes. In particular, about its requirement of space or memory. “Computers today are very fast and can also perform calculations in parallel. But the memory is still limited,” …

Continue Reading