Rust solution to http://www.reddit.com/r/dailyprogrammer/comments/2snhei/20150116_challenge_197_hard_crazy_professor/

crazy-professor.rs

use std::collections::HashSet;

/* /r/DailyProgrammer challenge #197 Hard
 * <http://www.reddit.com/r/dailyprogrammer/comments/2snhei/20150116_challenge_197_hard_crazy_professor/>
 * Goal: Find the 1,000,000th 20-smooth number: the one-millionth number that is not
 * divisible by any prime > 20
 */

trait Min<T: Ord> {
    fn min(&self) -> Option<T>;
}

impl<T: Ord + Clone> Min<T> for Vec<T> {
    fn min(&self) -> Option<T> {
        let mut it = self.iter();
        let mut n: T;
        match it.next() {
            Some(i) => n = (*i).clone(), // using `.clone()` feels cludgy...
            None => return None
        };
        loop {
            match it.next() {
                Some(x) => if (*x) < (n) {n = (*x).clone();},
                None => {break;}
            }
        };
        Some(n)
    }
}

// Sieve of Eratosthenes
// Returns a vector of all primes up to `n`
fn psieve(n: usize) -> Vec<usize> {
    let mut unprimes = HashSet::new();
    let mut primes: Vec<usize> = vec![];
    for num in 2..(n + 1) {
        if !unprimes.contains(&num) {
            primes.push(num);
            let mut counter = num + num;
            while counter <= n {
                unprimes.insert(counter);
                counter += num;
            }
        }
    }
    primes
}

#[derive(Show)]
struct SmoothNumGenerator {
    // Generate B-smooth numbers
    B: usize,
    // the primes <= B
    primes: Vec<usize>,
    // iterator indices
    iters: Vec<usize>,
    // next values for each prime
    nexts: Vec<usize>,
    // memoized list of numbers
    values: Vec<usize>,
    // current index
    n: usize
}


impl SmoothNumGenerator {
    fn new(n: usize) -> SmoothNumGenerator {
        let primes = psieve(n);
        let ns = primes.iter().map(|_| 1).collect();
        let is = primes.iter().map(|_| 0).collect();
        SmoothNumGenerator{B: n,
                           primes: psieve(n),
                           iters: is,
                           nexts: ns,
                           values: vec![1],
                           n: 0}
    }

    fn next(&mut self) -> usize {
        self.n += 1;
        let m = self.nexts.min().expect("Should *always* have another value");
        self.values.push(m);
        for (idx, prime) in self.primes.iter().enumerate() {
            if self.nexts[idx] == m {
                self.iters[idx] += 1;
                self.nexts[idx] = (*prime) * self.values[self.iters[idx]];
            }
        }
        m
    }
}

fn main() {
    let mut sng = SmoothNumGenerator::new(20);
    let mut i = 0;
    let limit = 1000000 - 1;
    while i < limit {
        i += 1;
        sng.next();
    }
    println!("{}", sng.next());
}