# Initialize a Sieve of Eratosthenes in Scala

I am learning Scala while solving some exercises and I am currently solving an exercise where I need to initialize a Sieve of Eratosthenes.

I am using the following code:

  val sieve = Array.fill[Boolean](100)(true)

for (p <- 2 until sieve.length if sieve(p) && math.pow(p, 2) <= sieve.length) {
for (i <- p * 2 until sieve.length by p) {
sieve(i) = false
}
}


I see some problems with this approach, for example, the outer loop still evaluates all numbers from some Y until sieve.length to test the condition sieve(p) && math.pow(p,2) <= sieve.length, although the code inside the loop is not executed for those values of p.

I think this could be solved with the following code:

 var p = 2
while(math.pow(p, 2) <= sieve.length)
{
if(sieve(p))
for (i <- p * 2 until sieve.length by p)
sieve(i) = false

p += 1
}


I may be wrong, but I think I am complicating too much.

What's a good way to initialize a Sieve of Eratosthenes using Scala?

There are many other ways of writing a Sieve of Eratosthenes in Scala. Regarding this particular code, the for-comprehension is better written as:

val sieve = Array.fill[Boolean](100)(true)

for {
p <- 2 until sieve.length
if sieve(p) && math.pow(p, 2) <= sieve.length
i <- p * 2 until sieve.length by p
} sieve(i) = false


Also,

the outer loop still evaluates all numbers from some Y until sieve.length to test the condition sieve(p) && math.pow(p,2) <= sieve.length,

You could compute the square root too, though that's an expensive computation. You can use takeWhile to avoid it:

p <- 2 until sieve.length takeWhile (x => x * x < sieve.length)


Also, the starting place of the final loop can be improved:

i <- p * p until sieve.length by p


Altogether, you get this:

val sieve = Array.fill[Boolean](100)(true)

for {
p <- 2 until sieve.length takeWhile (x => x * x < sieve.length)
if sieve(p)
i <- p * p until sieve.length by p
} sieve(i) = false


Now, I wouldn't use booleans for this, nor an Array. Instead, my preferred implementation (for efficiency) uses BitSet instead. For example:

val last = 100
val numbers = 2 to last
val sieve = collection.mutable.BitSet(numbers: _*)
for (p <- numbers takeWhile (x => x * x <= last) if sieve(p))
sieve --= p * p to last by p


There are other implementations I value for their functional nature, but I'll leave that to others.

• Thanks, I didn't know I could pass a {} block to a for like that. How about the _* you used to initialize the BitSet, where is that documented? – simao Aug 7 '11 at 0:28
• @simao you'll probably find that documented where varargs are discussed. It is just a wa of saying that the sequence elements are the parameters, instead of the sequence itself being one parameter. – Daniel C. Sobral Aug 7 '11 at 16:20
• ah! so i guess it's like python's *args and **kwargs syntax. Thanks! – simao Aug 7 '11 at 16:22