Improving on the Sieve of Eratosthenes
johndcook.com
Improving on the Sieve of Eratosthenes
1–6 of 6 posts
Re: Improving on the Sieve of Eratosthenes
#2Re: Improving on the Sieve of Eratosthenes
#3https://arxiv.org/abs/1712.09130
Thanks. I found it odd that the author didn’t include a link to the paper.
Re: Improving on the Sieve of Eratosthenes
#4https://arxiv.org/abs/1712.09130
Thanks. I found it odd that the author didn’t include a link to the paper.
They did provide a link to it in the references, no?
Re: Improving on the Sieve of Eratosthenes
#5"[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))
Re: Improving on the Sieve of Eratosthenes
#6This article has no substance.
"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."