Anonymous user
Talk:Sieve of Eratosthenes: Difference between revisions
→Java
(→Java) |
(→Java) |
||
Line 92:
}</lang>
The problem here is the concept of removing values. Even the "optimisation" of filling nums with odd values is no optimisation at all. Trying to sieve 40004 for the posted algorithm takes around 3.292s ("optimised") while the algorithm above takes 0.006s and the bitset sieve clocks at 0.008s. Thanks --[[User:Xelamitchell|xelamitchell]] 19:50, 7 October 2013 (UTC)
... Except that the above Java code isn't a ''Sieve of Eratosthenes''. A ''SoE'' algorithm doesn't '''TEST''' for primality, it ''just'' removes all composites (and sometimes unity); what's left is a (somehow marked/indicated) list/array of primes [up to the (original) highest element in the list/array of integers]. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 22:50, 7 October 2013 (UTC)
:Hmm, I'm not sure. If by primality check you mean the line "if(isPrime[i])" then it is doing the same work of the posted code's "nums.remove()" (finding the next valid prime to begin marking, it is not a method merely a reference to the array) only much more efficiently. Also my code is truer to the algorithm (in terms of algorithmic description, pseudocode, end representation (having a marked list of values and a separate list of collected primes by the end of the run) and performance) as described in [http://en.wikipedia.org/wiki/Sieve_of_eratosthenes Wikipedia - Sieve of Eratosthenes] than the posted code. I don't know where you got the requirement that composites must be removed, the original algorithm merely states they must be '''marked iteratively'''. --[[User:Xelamitchell|xelamitchell]] 10:22, 8 October 2013 (UTC)
| |||