Ancient algorithm
Eratosthenes had a good idea for finding all primes less than an upper bound N over 22 centuries ago.
Make a list of the numbers 2 to N. Circle 2, then scratch out all the larger multiples of 2 up to N. Then move on to 3. Circle it, and scratch out all the larger multiples of 3.
Every time you start over and find a number that hasn’t been scratched out before, that means it’s not divisible by any numbers smaller than itself, so it’s prime. Circle it and repeat. This algorithm is known as the sieve of Eratosthenes.
You could turn this into an algorithm for factoring every number less than N by not just scratching off composite numbers but keeping track of what numbers they were divisible by.
Not bad for an algorithm that predates Hindu-Arabic numerals by nine centuries. But as you might imagine, there have been a few improvements over the last couple millennia.
New algorithm
A paper by Helfgott published last week [1] gives a refined version of the sieve that takes less time and less space. Helfgott is not the first to improve on the sieve of Eratosthenes, but the latest.
His paper shows that it is possible to find all primes less than N in time
O(N log N)
and space
O(N1/3 (log N)2/3).
Furthermore, it is possible to factor all integers less than N in time
O(N log N)
and space
O(N1/3 (log N)5/3).
He also addresses finding all primes and factoring all integers in an interval [N – Δ, N + Δ] provided
N1/3 (log N)2/3 ≤ Δ ≤ N.
In the case of such an interval, one can find all the primes in the interval in time O(Δ log N) and space O(Δ). And one can factor all integers in the interval in time and space O(Δ log N).
Helfgott’s paper gives detailed pseudocode for all the algorithms.
Related posts
- Odd Goldbach conjecture (proved by Helfgott)
- Big O tilde notation
[1] Harald Andrés Helfgott. An improved sieve of Eratosthenes, Mathematics of Computation, https://doi.org/10.1090/mcom/3438. Published online April 23, 2019.
preprint version: https://arxiv.org/abs/1712.09130
Hello, can you give me an specific example of what consist this improving of the Eratosthenes Sieve?
For example, if I have a number N, is it only necessary test if that number is divisible for some prime number lower than N^(1/3) (log N) ^(2/3) instead of lower than N^(1/2) for know if N is a prime number?