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 &lt;- 2 until sieve.length if sieve(p) &amp;&amp; math.pow(p, 2) &lt;= sieve.length) {
    for (i &lt;- 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) &amp;&amp; math.pow(p,2) &lt;= 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) &lt;= sieve.length)
 {
   if(sieve(p))
     for (i &lt;- 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 &lt;- 2 until sieve.length 
  if sieve(p) &amp;&amp; math.pow(p, 2) &lt;= sieve.length
  i &lt;- 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) &amp;&amp; math.pow(p,2) &lt;=
  sieve.length,


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

p &lt;- 2 until sieve.length takeWhile (x =&gt; x * x &lt; sieve.length)


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

i &lt;- p * p until sieve.length by p


Altogether, you get this:

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

for {
  p &lt;- 2 until sieve.length takeWhile (x =&gt; x * x &lt; sieve.length)
  if sieve(p)
  i &lt;- 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 &lt;- numbers takeWhile (x =&gt; x * x &lt;= 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.