Scalaで素数判定（1）

Pythonと同じことをします。
まずは試し割りから。

def is_prime1(n :Int) :Boolean =
    Iterator.from(2).takeWhile(p => p * p <= n).forall(p => n % p != 0)

def make_primes(N :Int, is_prime :Int => Boolean) :List[Int] =
    Iterator.range(2, N + 1).filter(is_prime).toList

def solve() = {
    val primes = make_primes(N, is_prime1)
    println (N, primes.size)
}

object Test extends Benchmark {
    def run() = solve
}

val N = 1e6.toInt
val ts = Test.runBenchmark(10)
println (ts)
println (ts.slice(5, 10).sum / 5)

772

10回計測して後ろ5回の平均を取っています。Pythonより30倍以上速いですね。
ScalaではtakeWhileは遅くないのでしょうか。

def is_prime1a(n :Int) :Boolean = {
    val limit_p = sqrt(n.toDouble).toInt
    Iterator.range(2, limit_p + 1).forall(p => n % p != 0)
}

577

Pythonほど極端な差は出なくともtakeWhileはやっぱり遅いんですね。これだとPythonの17倍ですね。奇数で割っていく方法だと283msでした。あらかじめ用意した素数で割っていく方法だと、

def is_prime3(n :Int) :Boolean =
    primes.takeWhile(p => p * p <= n).forall(p => n % p != 0)

1432

めちゃくちゃ遅いですね。なんでですかねえ。そうか、primesはリストだからforall関係なくtakeWhileが処理されるんですね。Iteratorにすれば遅延評価が行われて、forallでfalseになればこれ以上takeWhileは処理されないはずです。

def is_prime3a(n :Int) :Boolean =
    primes.toIterator.takeWhile(p => p * p <= n).forall(p => n % p != 0)

935

う〜ん、遅いですねえ。どうもScalaはIteratorが遅そうです。どうしたらいいんでしょう。そういえばリストは再帰と相性がいいんでしたね。

def is_prime3b(n :Int) :Boolean = {
    def f(ps :List[Int]) :Boolean = ps match {
        case Nil => true
        case p :: tail if p * p > n => true
        case p :: tail if n % p == 0 => false
        case p :: tail => f(tail)
    }
    
    f(primes)
}

76

えー！いやいやそんなわけないだろ。奇数で割る方法で再帰を使うと、

def is_prime2a(n :Int) :Boolean = {
    def f(p :Int) :Boolean =
        if(p * p > n)       true
        else if(n % p == 0) false
        else if(p == 2)     f(p + 1)
        else                f(p + 2)
    
    f(2)
}

142

とにかく再帰だと速いみたいですねえ。というか、takeWhileとforallが遅そうですね。これを使えば1行で書けるのに。