Talk:Sieve of Eratosthenes: Difference between revisions
→Trial division sieves should be moved from here: add emphasis , c/e
(→Trial division sieves should be moved from here: Fix font in last reply) |
(→Trial division sieves should be moved from here: add emphasis , c/e) |
||
Line 153:
It is most definitely a sieve, just not the sieve of Eratosthenes as it is understood today, and at least as early as 1772 -- time of publication of the article by Horsley, referenced in the Wikipedia article, in which he much trashes Nicomachus (yes, trashes, it is beyond criticism), incidentally, for being unable to convey clearly the essence of Eratosthenes's method.
'''It indeed is a ''trial division'' sieve - a sieve where the removal is done by trying out''' (for each candidate number, in separation, one after the other) '''the divisions''' by primes, one prime after another, as opposed to the "true" sieve of Eratosthenes finding out the composites as primes' multiples, and getting the primes for free, in the gaps between the multiples, as "what's left" after all the numbers are let ''through "the sieve"'' (when holes are made under the composites).
I.e. in the proper SoE '''the sieve is ''constructed'' (for a range of numbers as a whole) from primes, by ''counting'' (i.e. by repeated additions); no number needs be attempted to be divided by any other number. And that's the difference between the two.'''
A defining characteristic of an algorithm is its theoretical time complexity. The sieve of Eratosthenes' complexity is N log (log N) ~ n log n log (log n), for n primes below N; the (''optimal'') trial division sieve's - N^1.5/(log N)^2 ~ n^1.5/(log n)^0.5, as derived in M. O'Neill's paper. Granted, that paper is short on clear-cut explanations, but it has the needed math derivations nonetheless.
| |||