3
\$\begingroup\$

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?

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – simao Aug 7 '11 at 0:28
  • \$\begingroup\$ @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. \$\endgroup\$ – Daniel C. Sobral Aug 7 '11 at 16:20
  • \$\begingroup\$ ah! so i guess it's like python's *args and **kwargs syntax. Thanks! \$\endgroup\$ – simao Aug 7 '11 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.