Project Euler #95 (Rust)

amicable.rs

use std::cmp::min;
use std::usize::MAX as NUM_MAX;

const MAX: usize = 1000000;

fn main() {
    // statically-allocated list used by `amicable` to mark numbers
    let mut marks = [0; MAX + 1];
    let (min, len) = (1..marks.len())
        .flat_map(|n| amicable(n, &mut marks)) // flat map to ignore `None`s
        .inspect(|v| println!("-> {:?}", v)) // print out newly found cycles
        .max_by_key(|&(_, l)| l)
        .unwrap(); // unwrap because max is `Option` (case when no elements)
    println!("Found cycle with len: {} and min: {}", len, min);
}

// `amicable` marks each number `v` it encounters by setting `marks[v]` to `n`.
// This way it can detect previously evaluated numbers (marked with neither `n` nor 0)
// and cycles (already marked with `n`). None is returned when no new information is avalable.
fn amicable(n: usize, marks: &mut [usize]) -> Option<(usize, usize)> {
    let mut v = n; // current number (must keep hold of `n`)
    // first loop desends until it finds a previously seen number (marked with own `n`)
    loop {
        if marks[v] == n { break } // we are in a cycle!
        if marks[v] != 0 { return None } // number already processed
        marks[v] = n; // mark number with `n`
        v = factor_sum(v); // move forward
        if v >= marks.len() { return None } // prevent overflow
    }

    // second loop counts cycle length and finds min number
    let mut bot = NUM_MAX; // keep track of smallest number in cycle
    let mut e = v; // current number (mut keep hold of v)
    for count in 1.. {
        bot = min(e, bot); // take the min
        e = factor_sum(e); // step forward
        if e == v { return Some((bot, count)) } // if back to where we were before loop
    }
    unreachable!()
}

fn factor_sum(n: usize) -> usize {
    let top = (n as f32).sqrt() as usize; // could be much faster
    (2..top)
        .filter(|v| n % v == 0)
        .flat_map(|v| vec![v, n / v])
        .sum::<usize>() + 1 // 1 is a divisor, but we started with 2
}