Scalaでエラトステネスのふるい

Scala

何番煎じだよってカンジですね。

  • Nまでの素数がほしい
import scala.annotation.tailrec

object Main {
	def main(args: Array[String]) {
		val sieve = (n: Int) => {
			@tailrec
			def inner(ls: List[Int], acc: List[Int], end: Int): List[Int] = {
				val x = ls.head
				val xs = ls.tail
				if (x * x <= end) {
					inner(xs.filter(_ % x != 0), x :: acc, end)
				} else acc.reverse ++ ls
			}
			inner((2 to n).toList, Nil, n)
		}

		println(sieve(10000))
	}
}

自分はこれくらいの速度で十分なので、基本的にこれを使うつもり。

  • N番目までの素数がほしい
object Main {
	def main(args: Array[String]) {
		val sieve = (n: Int) => {
			def inner(ls: Stream[Int]): Stream[Int] = {
				val x = ls.head
				val xs = ls.tail
				Stream.cons(x, inner(xs.filter(p => p < x * x || p % x != 0)))
			}
			inner(Stream.from(2)).take(n).toList
		}

		println(sieve(1000))
	}
}

Haskellでの実装をマネしてみました。
Streamを使ってみたのですが、おもしろいですね、これ。
ただ、再帰が増えていったときにスタックがどうなっているのかは気になるところです。