September 24, 2016
4 min read
New Take on an Ancient Method Improves Way to Find Prime Numbers
The modified version of the sieve of Eratosthenes could accelerate computer calculations
By Matías Loewy
Peruvian mathematician Harald Helfgott gained worldwide attention in 2013 when he solved a 271-year-old problem: the so-called Goldbach’s weak conjecture, according to which every odd number greater than 5 can be expressed as the sum of three prime numbers—such as: 3 + 3 + 5 = 11 and 19 + 13 + 3 = 35.
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.
On supporting science journalism
If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
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," Helfgott explains.
Mathematician Jean Carlos Cortissoz Iriarte, of Cornell University and Los Andes University, says that in order to know how good an algorithm is, one has to consider two factors: the number of operations per bit given an input (for example, 100) and the number of bits to be stored in memory while the instructions are executed. “In terms of the number of operations per bit to be performed, the sieve of Eratosthenes is relatively efficient. It grows in proportion to the size of the interval considered. But if you look at what needs to be kept in memory for each step of the algorithm performed for large intervals [numbers], then the sieve stops being efficient,” he says.
Now, inspired by combined approaches to the analytical 100-year-old technique called the circle method, Helfgott was able to modify the sieve of Eratosthenes to work with less physical memory space. In mathematical terms: instead of needing a space N, now it is enough to have the cube root of N. “To calculate all primes up to a trillion, the modified version of the sieve requires a few million bits instead of a billion bits,” Helfgott says. The main ideas of the proposal were presented in July both at the XXI Latin American Colloquium of Algebra, held in Buenos Aires, and at Sinapsis 2016, a confab of Peruvian scientists residing in Europe, held in Paris.
To understand the advantage of the new sieve, Cortissoz offers an analogy. “Let's pretend that you are a computer and that to store data in your memory you use sheets of paper. If to calculate the primes between 1 and 1,000,000, you need 200 reams of paper (10,000 sheets), and with the algorithm proposed by Helfgott you will only need one fifth of a ream (about 100 sheets),” he says.
Although reducing the space requirement generally implies certain “minor” sacrifices in the theoretical speed of the algorithm, Helfgott believes that in certain ranges the deficit could be offset or exceeded by the possibility of mainly or exclusively using the cache memory—which is smaller but faster than main memory or RAM. “It depends on the application,” he says.
There are other sieves or algorithms to identify prime numbers. But Helfgott notes the sieve of Eratosthenes is different in that it also can workwith other mathematical operations such as factorization—a technique that breaks down any number in the product of prime numbers and is the basis of cryptographic methods for encoding information in a safe way, such as for conducting electronic bank transfers or online purchases. “Factoring has become a key element of contemporary civilization,” Helfgott says. Eratosthenes would never have imagined it.
