sieve of eratosthenes


See On Github

Data

Source Code

package sieve_of_eratosthenes

object Sieve {

  /*
   * Given an upper bound, starting with 2, generate the list of integers up to that bound, extract
   * the head of that list and filter out those numbers that are divisible by the current head.
   * Repeat.
   */
  def sieveOfEratosthenes(upperBound: Int): Vector[Int] = {

    @annotation.tailrec
    def go(acc: Vector[Int], rem: List[Int]): Vector[Int] = rem match {
        case h :: t => go(acc :+ h, t.filterNot(i => i % h == 0))
        case _ => acc
      }

    go(Vector(), (2 to upperBound).toList)

  }

}

class Sieve_test extends WordSpec with Matchers {

  "The Sieve of Eratosthenes" should {

    "provide prime numbers up to a certain bound" in {
      val primesBelowOneHundred = Vector(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)

      val withSieve = sieveOfEratosthenes(100)

      withSieve.size shouldBe primesBelowOneHundred.size
      (withSieve zip primesBelowOneHundred).forall(t => t._1 == t._2) shouldBe true
    }
  }

}