"[the paper] gives a refined version of the sieve that takes less time and less space."
It is not about the time-complexity which is "almost" linear in any case (and even slightly worse than the classical version O(nlog(log(n)) vs O(nlog(n)), but about the space complexity, which is "almost" O(n^(1/3)) vs O(n^(1/2) ( or the classical "naive" O(n))
"Here's how the Sieve of Eratosthenes works. It can be improved upon and in fact X person did it recently. Said improvements are left as an exercise to the reader. The End."
5 comments
[ 3.1 ms ] story [ 19.5 ms ] threadhttps://doi.org/10.1090/mcom/3438
"Here's how the Sieve of Eratosthenes works. It can be improved upon and in fact X person did it recently. Said improvements are left as an exercise to the reader. The End."