Rust で ProjectEuler #4 ~ #7

Rust Project Euler

Problem 4

3桁の2つの数の積で表せる最大の palindrome な数。

use std;

fn to_palindromic(n: u64, dup_flag: bool) -> u64 {
    let cs = str::chars(u64::to_str(n, 10u));
    let s = str::from_chars(
        if dup_flag { cs + vec::tail(vec::reversed(cs)) } else { cs + vec::reversed(cs) }
    );
    alt u64::from_str(s, 10u) {
      none    { fail }
      some(x) { ret x }
    }
}

fn dividable_pairs(num: u64, min: u64, max: u64) -> [(u64, u64)] {
    let div = u64::max(uint::div_ceil(num, max), min);
    let result = [];
    while div * div <= num {
        if num % div == 0u64 {
            result += [(div, num / div)];
        }
        div += 1u64;
    }
    ret result;
}

fn main() {
    let dup_flag = false;
    while true {
        let seed = 999u64;
        while (seed >= 100u64) {
            let num = to_palindromic(seed, dup_flag);
            let pairs = dividable_pairs(num, 100u64, 999u64);
            if vec::is_not_empty(pairs) {
                std::io::print(#fmt("%u", num));
                for (d1, d2) in pairs {
                    std::io::print(#fmt(" = %u * %u", d1, d2));
                }
                std::io::print("\n");
            }
            seed -= 1u64;
        }
        if (!dup_flag) {
            dup_flag = true;
        } else {
            break
        }
    }
}

最大の数だけじゃなくて、すべての palindrome な数を列挙します。palindrome な数を大きな方から生成していって、3桁の数で割れるかどうか確かめています。特に凝ったことはしていません。

Problem 5

1~20の最小公倍数を求める

use std;

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

fn div_mult(&num: u64, f: u64) -> u64 {
    let exp = 0u64;
    while (num % f == 0u64) {
        exp += 1u64;
        num /= f;
    }
    ret exp;
}

fn factorize(num: u64, &primes: [u64]) -> [(u64, u64)] {
    let itr = num;
    let result = [];

    for p in primes {
        let exp = div_mult(itr, p);
        if exp > 0u64 {
            result += [(p, exp)];
        }
    }

    while itr != 1u64 {
        primes = gen_prime(primes);
        let p = vec::last_total(primes);
        let exp = div_mult(itr, p);
        if exp > 0u64 {
            result += [(p, exp)];
        }
    }

    ret result;
}

fn merge_fact(fs1: [(u64, u64)], fs2: [(u64, u64)]) -> [(u64, u64)] {
    let result = [];
    let i1 = 0u, i2 = 0u;
    let len1 = vec::len(fs1), len2 = vec::len(fs2);
    while (i1 < len1 && i2 < len2) {
        let (base1, exp1) = fs1[i1];
        let (base2, exp2) = fs2[i2];
        if (base1 < base2) {
            result += [(base1, exp1)];
            i1 += 1u64;
        } else if (base1 > base2) {
            result += [(base2, exp2)];
            i2 += 1u64;
        } else {
            result += [(base1, uint::max(exp1, exp2))];
            i1 += 1u64;
            i2 += 1u64;
        }
    }
    if i1 < len1 {
        result += vec::slice(fs1, i1, len1);
    }
    if i2 < len2 {
        result += vec::slice(fs2, i2, len2);
    }
    ret result;
}

fn merge_facti(fss: [[(u64, u64)]]) -> [(u64, u64)] {
    ret alt vec::len(fss) {
      0u64 { [] }
      1u64 { fss[0] }
      l    {
        let pre  = merge_facti(vec::slice(fss, 0u64, l / 2u64));
        let post = merge_facti(vec::slice(fss, l / 2u64, l));
        merge_fact(pre, post)
      }
    }
}

fn pow(base: u64, exp: u64) -> u64 {
    let result = 1u64;
    let itr = exp;
    let pow = base;
    while itr > 0u64 {
        if itr & 0x1u64 == 0x1u64 {
            result *= pow;
        }
        itr >>= 1u64;
        pow *= pow;
    }
    ret result;
}

fn fact_to_uint(fs: [(u64, u64)]) -> u64 {
    let result = 1u64;
    for (base, exp) in fs {
        result *= pow(base, exp);
    }
    ret result;
}

fn main() {
    let primes = [];
    let factors = vec::map(vec::enum_uints(1u64, 20u64)) { |num| factorize(num, primes) };
    std::io::println(#fmt("%u", fact_to_uint(merge_facti(factors))));
}

1〜20の数を素因数分解して、それらの因数をマージして、最後に掛けています。

Problem 6

1~100の数字の「二乗和」と「和の二乗」の差を求める。

use std;

fn sum_of_square(n: u64) -> u64 {
    ret n * (n + 1u64) * (2u64 * n + 1u64) / 6u64;
}

fn sum_of_seq(n: u64) -> u64 {
    ret n * (n + 1u64) / 2u64;
}

fn square_of_sum(n: u64) -> u64 {
    let s = sum_of_seq(n);
    ret s * s;
}

fn main() {
    let sq_of_sum = square_of_sum(100u64);
    let sum_of_sq = sum_of_square(100u64);
    std::io::println(#fmt("%u - %u = %u", sq_of_sum, sum_of_sq, sq_of_sum - sum_of_sq));
}

二乗和には以下の公式を用いました。高校でやりましたね！
\Sigma_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}

Problem 7

1001番目の素数を求める。

use std;
use util;

fn gen_prime(&primes: [u64]) {
    let num = alt vec::last(primes) {
      none       { primes =  [2u64]; ret }
      some(2u64) { primes += [3u64]; ret }
      some(x)    { x + 2u64 }
    };

    while true {
        for p in primes {
            if p * p > num {
                primes += [num];
                ret;
            }
            if num % p == 0u64 {
                break;
            }
        }
        num += 2u64;
    }
    fail;
}

fn main() {
    let idx = 10000u64;
    let primes = [];
    uint::range(0u64, idx + 1u64) { |_num|
        gen_prime(primes);
    }
    std::io::println(#fmt("%u", primes[idx]));
}