PRIME numbers may have been studied for over 2000 years, but there is always something new to learn. A method for finding primes first devised by the ancient Greek mathematician Eratosthenes in 240 BC has had a 21st century upgrade.
Prime numbers are divisible only by themselves and 1, and form the building blocks of all other numbers 鈥� multiplying different primes creates the rest聽of the whole numbers.
The Sieve of Eratosthenes, as聽it is known, lets you find all prime numbers less than a certain number by sequentially sieving out multiples of primes.
Advertisement
For example, for the numbers 1 to 100, you would begin by removing all multiples of 2, the first prime number 鈥� so 4, 6, 8 and so on. You would then start again from the next smallest number, removing multiples of聽3. Each number you begin the聽process on 鈥� a number that hasn鈥檛 already been removed 鈥� is prime.
The sieve works well for finding small primes, but becomes unworkable for very large ones because of the time and computer memory required.
In the 1960s, when computers had far less memory聽than they do now, mathematicians optimised the sieve so that they could find all prime numbers up to a certain number, N, while using only 鈭歂聽units of storage space. For example, to find all the prime numbers up to 100, an algorithm could store and process numbers in rows of 10.
But that isn鈥檛 practical for much larger values of N. 鈥淵ou can鈥檛 do that for a billion numbers using only 10 units of聽space at a time, because the聽algorithm becomes very inefficient,鈥� says Harald Helfgott at the University of G枚ttingen in聽Germany, who has upgraded the method.
His work uses Diophantine approximation, where real numbers 鈥� essentially any point on the number line, including decimals 鈥� can be approximated by rational numbers 鈥� those that can be expressed as a fraction of聽two whole numbers. Pi, for example, is a real number that can be approximated by the fraction 355/113.
This lets Helfgott sieve across a range of numbers at the same time, making the process more efficient. To find all primes less than a number N, the algorithm requires less computer memory 鈥� about N1/3(log N)2/3 units of storage space. It would let you sieve a billion numbers with around 7500 units of memory compared with about 32,000 for the existing method (Mathematics of Computation, ).
Helfgott鈥檚 approach can also be used to factorise very large numbers, breaking them down into prime building blocks. It is not yet clear if Helfgott鈥檚 approach will be practically useful, as he has not optimised his algorithm.
鈥淗ow much of a difference it makes in practice we will only know once real programmers implement the program and spend time optimising it,鈥� he聽says.
Article amended on 16 May 2019
We corrected the reason for the gains being purely theoretical
