Rust で ProjectEuler #1 ~ #3

Rust Project Euler

放置状態になっていたProject Eulerを再開してみることにしました。以前はHaskellでProb. 133まで解いてHaskellに慣れることができたので、今回はRustで書いてみようと思います。Haskellは最後まで使いこなせてる感は出なかったのですが、遅延評価ではないRustなら直感的に計算量とか理解できてやりやすいはず…？
というわけで、解いていきます

Problem 1

1000以下の数字で3か5で割り切れるものの和を求める問題。最初なので素直に書いた。

use std;

fn main() {
    let sum = 0u;
    uint::range(0u, 1000u) { |n|
        if n % 3u == 0u || n % 5u == 0u {
            sum += n;
        }
    }
    std::io::println(#fmt("%u", sum));
}

特に特筆事項は無い。

Problem 2

400万以下で偶数のフィボナッチ数の和を求める問題。

use std;

pure fn fib(prev: uint, cur: uint) -> (uint, uint) {
    ret (cur, prev + cur);
}

fn main() {
    const MAX: uint = 4000000u;
    let (prev, cur) = (1u, 1u);
    let sum = 0u;
    while cur < MAX {
        if (cur % 2u == 0u) {
            sum += cur;
        }
        let (prev2, cur2) = fib(prev, cur);
        prev = prev2;
        cur = cur2;
    }
    std::io::println(#fmt("%u", sum));
}

これも普通ですね。本当は

(prev, cur) = fib(prev, cur);

って書きたかったんですが、少なくとも現時点では、この方法では分割代入はできないみたいです。

Problem 3

600851475143 の最大の素因数を求める問題。

use std;

fn gen_prime(primes: [mutable u64]) -> [mutable u64] {
    let num = alt vec::last(primes) {
      none       { ret [mutable 2u64] }
      some(2u64) { ret primes + [mutable 3u64] }
      some(x)    { x + 2u64 }
    };
    while true {
        for p in primes {
            if p * p > num {
                ret primes + [mutable num];
            }
            if num % p == 0u64 {
                break;
            }
        }
        num += 2u64;
    }
    fail;
}

fn main() {
    let primes = gen_prime([mutable]);
    let num = 600851475143u64;
    while num != 1u64 {
        check vec::is_not_empty(primes);
        let p = vec::last_total(primes);
        while num % p == 0u64 {
            num /= p;
            std::io::println(#fmt("%u", p));
        }
        primes = gen_prime(primes);
    }
}

エラトステネスの篩で素数リストを作って、先頭から割っていっています。
二分探索がうまく動かなくて何度も書き直したのはここだけの秘密。境界条件はちゃんと考えてから書かないとだめですね。
とりあえず、最初のエントリはここまで。これからどんどんエントリ立てて行く予定。専用ブログ作ってもいいのかも。