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  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  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  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.

StackExchange Code Review Q#3850, answer score: 6