Sieve of Eratosthenes: Difference between revisions

val primes = collection.mutable.BitSet.empty.par ++ (2 to nTo)

candidate <- 2 to Math.sqrt(nTo).toInt

// BitSet toList is shuffled when using the ParSet version.

println(sieveOfEratosthenes(100).toList.sorted)</lang>

{{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)</pre>

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>