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āt 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 āNĀ 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āt practical for much larger values of N. āYou canāt 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ās approach can also be used to factorise very large numbers, breaking them down into prime building blocks. It is not yet clear if Helfgottās approach will be practically useful, as he has not optimised his algorithm.
āHow 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
