ScalaでProject Euler（7）

Problem 3

素因数分解して最後の素因数を表示すればよいでしょう。

Long

今まで使ってきたIntは32ビット符号付き整数です。与えられた整数はその範囲を超えています。Scalaには64ビット符号付き整数も用意されています。それがLongです。サフィックスLをつければLongになります。

val N = 600851475143L

List

ListはHaskellのそれと同じで、先頭からアクセスしていく列です。Listはこんな感じで作ります。

val a = List(3, 1, 4)

次は、先頭に要素をつけて新たなListを作っています。

val b = 5 :: a      // List(5, 3, 1, 4)

先頭の要素はheadで取り出し、先頭の次からのListはtailです。

val n = b.head      // 5
val c = b.tail      // List(3, 1, 4)

さて、素因数分解は短い列にしかなりえないので、実体のある列を使ってもよいでしょう。2から順に割っていって商が除数の自乗より小さくなればそこで終わりです。

def factorize(n :Long, p :Long = 2L) :List[Long] =
    if(n == 1)
        Nil
    else if(p * p > n)
        List(n)
    else if(n % p == 0)
        n :: factorize(n / p, p)
    else
        factorize(n, p + 1)

val N = 600851475143L
val fs = factorize(N)
println (fs.last)

Nilは空リスト、lastは最後の要素です。再帰だと戻り値の型推論してくれないんですね。Haskellなら。