ScalaでProject Euler（21）

Problem 12

500くらいなら前回の方法でも十分ですが、さらに大きくなると素数を求めるのにエラトステネスのふるいを使いたくなります。無限の素数列を作りたいので、例えば0〜99999までのエラトステネスのふるいをまず行って、そこまでの素数が尽きたら100000〜199999までのエラトステネスのふるいを行う、というようなことを繰り返します。

この考え方でStreamを作ろうとしましたがうまくいかなかったので、考え方を変えてシングルトンオブジェクトを作ることにしました。

Primes(2)

とすれば、3番目の素数が返るようにします。

ArrayBuffer

素数の列を保持しなければならないので、STLのvectorのような可変長の配列が必要です。これにはArrayBufferを使うのがよいようです。

import scala.collection.mutable.ArrayBuffer

val a = new ArrayBuffer[Int]
a += 1
a += 2
a ++= a
println (a)         // ArrayBuffer(1, 2, 1, 2)
println (a(3))      // 2
println (a.size)    // 4

シングルトンオブジェクト

これはclassの定義でclassと書くところをobjectと書けばよいだけのようです。素数を計算するより簡単なフィボナッチ数列の項を出力するシングルトンオブジェクトを例にします。

import scala.collection.mutable.ArrayBuffer

object Fibonacci {
    private val fibs = new ArrayBuffer[Int]
    fibs ++= ArrayBuffer(1, 1)
    
    def apply(n :Int) = {
        if(n >= fibs.size) {
            for(k <- (fibs.size) to n)
                fibs += fibs(k - 1) + fibs(k - 2)
        }
        fibs(n)
    }
}

println (Fibonacci(10))     // 89

applyは特殊なメソッドで、最後の行は

println (Fibonacci.apply(10))

と同じです。
素因数分解も繰り返しエラトステネスのふるい的なアルゴリズムを適用して計算します。ただし、一度しか出力する必要がないので、Iteratorとしました。
必要な計算だけLongで行い、約数の個数5000で計算できました。前回のコードではなぜかメモリが足らずに落ちました。

import scala.collection.mutable.ArrayBuffer

type Facts = List[(Int,Int)]

object Primes {
    private val primes = new ArrayBuffer[Int]
    private val L = 1e5.toInt
    private var offs = 0
    
    def apply(n :Int) = {
        if(n >= primes.size)
            sieve
        primes(n)
    }
    
    private def sieve() = {
        if(offs == 0)
            sieve_1st
        else
            sieve_2nd_or_later
        offs += L
    }
    
    private def sieve_1st() = {
        val a = new Array[Boolean](L)
        for(i <- 2 to (L - 1)) a(i) = true
        for(p <- 2 to (L - 1) if a(p);
                    m <- (p * 2) to (L - 1) by p)
            a(m) = false
        
        primes ++= (2 to (L - 1)).filter(a(_)).toArray
    }
    
    private def sieve_2nd_or_later() = {
        val N = offs + L - 1
        val a = new Array[Boolean](L)
        for(i <- 0 to (L - 1)) a(i) = true
        for(p <- primes.takeWhile(p => p * p <= N);
                    m <- ((offs + p - 1) / p * p) to N by p)
            a(m - offs) = false
        
        primes ++= (offs to N).filter(k => a(k - offs)).toArray
    }
}

class genFactors extends Iterator[Facts] {
    private val L = 1e5.toInt
    private val b = new Array[Facts](L)
    private var offs = 1
    private var k = 0
    
    def hasNext() = true
    
    def next() = {
        k += 1
        if(k >= offs)
            sieve
        b(k - offs + L)
    }
    
    private def sieve() = {
        val N = offs + L - 1
        val a = (offs to N).toArray
        for(i <- 0 to (L - 1)) b(i) = Nil
        for(p <- (0 to N).map(Primes(_)).takeWhile(p => p * p <= N);
                            m <- ((offs + p - 1) / p * p) to N by p) {
            val (q, e) = div_pow(a(m - offs), p)
            a(m - offs) = q
            b(m - offs) = (p, e) :: b(m - offs)
        }
        
        for(i <- 0 to (L - 1) if a(i) > 1)
            b(i) = (a(i), 1) :: b(i)
        
        offs += L
    }
    
    private def div_pow(n :Int, p :Int, e :Int = 0) :(Int,Int) =
        if(n % p != 0) (n, e) else div_pow(n / p, p, e + 1)
}

class genTriangleFactors extends Iterator[Facts] {
    val gf = (new genFactors).map(half)
    var prev = gf.next
    
    def hasNext() = true
    
    def next() = {
        val f = gf.next
        val g = prev ++ f
        prev = f
        g
    }
}

def half(f :Facts) :Facts = f match {
    case Nil => Nil
    case (2, 1) :: g => g
    case (2, e) :: g => (2, e - 1) :: g
    case h :: g => h :: half(g)
}

def pow(n :Int, e :Int) = (1 to e).foldLeft(1)((x, y) => x * n)

def num_divs(f :Facts) = f.foldLeft(1)((x, y) => x * (y._2 + 1))

def value(f :Facts) =
    f.foldLeft(1L)((x, y) => x * pow(y._1, y._2))

val N = 5000
val gt = new genTriangleFactors
println (gt.filter(x => num_divs(x) > N).map(value).next())