Project Euler 3 - inamori’s diary

http://projecteuler.net/index.php?section=problems&id=3

最大の素数を求めればよいのですが、せっかくなので素因数分解のコードを書きました。あまりうまく書けていません。

let rec calc_exp n p =
   if n % p = 0 then
      let t = calc_exp (n / p) p
      (fst t + 1, snd t)
   else
      (0, n)

let rec fac n p =
    if n = 1 then
        []
   else if p * p > n then
      [(n, 1)]
   else
      let t = calc_exp n p
      if fst t > 0 then
         (p, fst t) :: (fac (snd t) (p + 1))
      else
         fac n (p + 1)

let factorize n = fac n 2

let f = factorize 13195
printfn "%d" (fst (f.[f.Length-1]))

ここも3タブにしています。
リストのインデックス参照は、

list.[index]

とします。
上は例題を解いていますが、このまま問題にあてはめると、

let f = factorize 600851475143

32ビット整数の範囲外と怒られてしまいました。Haskellのように適当に判断してくれません。サフィックスがない整数は32ビット整数とみなされます。64ビット整数を使いたい場合はサフィックスLをつけます。

let f = factorize 600851475143L

しかしこれだとintのはずがint64だと怒られます。どうやらCなどと違って勝手に型変換はしてくれないようです。必要なところはint64にしなければなりません。片っ端からLをつけて、

let rec calc_exp n p =
   if n % p = 0 then
      let t = calc_exp (n / p) p
      (fst t + 1, snd t)
   else
      (0, n)

let rec fac n p =
    if n = 1L then
        []
   else if p * p > n then
      [(n, 1)]
   else
      let t = calc_exp n p
      if fst t > 0 then
         (p, fst t) :: (fac (snd t) (p + 1L))
      else
         fac n (p + 1L)

let factorize n = fac n 2L

let f = factorize 600851475143L
printfn "%d" (fst (f.[f.Length-1]))

まだ型が合わないとコンパイラに怒られます。こういうときコンパイラは大抵的外れところを指摘して、本当に間違っているところはわかりません。
こういうときの定番の解決方法は型を指定することです。型指定しなくても型推論で型を決めてくれるはずなのですが、コードのどこかが間違っていると意図していない型に解釈される可能性があります。これを排除するために型を指定します。例えば、

let f n = n + 1

は引数と戻り値の型を書くと、

let f (n : int) : int = n + 1

となります。intは32ビット符号付き整数です。64ビット版はint64です。ここで、素因数分解の結果はint64（素数）とint（指数）のタプルのリストで返すようにしています。タプルの型は、

int64 * int

と表します。タプルは直積を意味するみたいな感じでしょうか。そしてリストは、

(int64 * int) list

です。型を元のコードにいくつか付けてみてコンパイルしたところ次のようなエラーメッセージが出ました。

euler003.fs(2,15): error FS0001: This expression was expected to have type
    int64
but here has type
    int

2行目の15文字目、

  if n % p = 0 then

0にLがついていなかったんですね。これで正しく答えが出ます。

let rec calc_exp (n : int64) (p : int64) : int * int64 =
   if n % p = 0L then
      let t = calc_exp (n / p) p
      (fst t + 1, snd t)
   else
      (0, n)

let rec fac n p : (int64 * int) list =
    if n = 1L then
        []
   else if p * p > n then
      [(n, 1)]
   else
      let t = calc_exp n p
      if fst t > 0 then
         (p, fst t) :: (fac (snd t) (p + 1L))
      else
         fac n (p + 1L)

let factorize (n : int64) : (int64 * int) list = fac n 2L

let f = factorize 600851475143L
printfn "%d" (fst (f.[f.Length-1]))