Sieve of Eratosthenes: Difference between revisions
→{{header|Scala}}: corrected 'true' code, comments, added a much faster array version
GordonBGood (talk | contribs) (→Infinite list using generators: note that is trial division not Eratosthenes...) |
GordonBGood (talk | contribs) (→{{header|Scala}}: corrected 'true' code, comments, added a much faster array version) |
||
Line 4,433:
=={{header|Scala}}==
=== Genuine Eratosthenes sieve===
<lang Scala>def sieveOfEratosthenes(nTo: Int) = {
val primes = collection.mutable.BitSet.empty.par ++ (2
for {
candidate <-
if primes contains candidate
} primes --= candidate * candidate to nTo by candidate
primes
}
// BitSet toList is shuffled when using the ParSet version.
println(sieveOfEratosthenes(
{{out}}
<pre>List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
The above code is quite slow but a little faster not using the ParSet (taking out the '.par'), in which case the conversion 'toList' and sorting ('sorted') are not necessary; the above code also uses a lot of memory with an Int element in the BitSet for every number in the range for which the composite numbers are removed by the sieve operation.
The below code using an array (bit packed) is 10's of times faster and uses 32 times less memory:
<lang Scala>def sieveOfEratosthenes(nTo: Int) = {
val nonprimes = new java.util.BitSet(nTo + 1)
Iterator.iterate(2)(p => nonprimes.nextClearBit(p + 1))
.takeWhile(_ <= Math.sqrt(nTo).toInt).foreach(p => {
for {cull <- p * p to nTo by p} nonprimes set cull })
Iterator.iterate(2)(p => nonprimes.nextClearBit(p + 1)).takeWhile(_ <= nTo) }</lang>
===Sub-optimal tail recursive trial division===
| |||