# Rust で ProjectEuler #4 ~ #7

#### 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
}
}
}


#### 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));
}


#### 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]));
}