素数アルゴリズム

PrimeNumber.scala

/**
 * 素数アルゴリズム
 *
 * エラトステネスの篩
 * - 整数のリストに2からxまでの数を入れる
 * - リストの先頭に行き、その数の倍数をふるい落とす
 * - リストの先頭の値がxの平方根になるまで繰り返す
 */
object PrimeNumber {
  def main(args: Array[String]) {
    val primes = (n: Int) => sieve((2 to n).toList)
    println(primes(100))
  }

  def sieve(xs: List[Int]): List[Int] = xs match {
    case x if x.isEmpty => Nil
    case _ => xs.head :: sieve(xs.tail.filter(_ % xs.head != 0))
  }
}