Discussion on: Project Euler #3 - Largest Prime Factor

[Idan Arye]

Rust:

struct PrimesIterator {
    found_primes: Vec<u64>,
    next_to_check: u64,
}

impl PrimesIterator {
    fn new() -> Self {
        PrimesIterator {
            found_primes: Vec::new(),
            next_to_check: 2,
        }
    }
}

impl Iterator for PrimesIterator {
    type Item = u64;
    fn next(&mut self) -> Option<u64> {
        for num in self.next_to_check.. {
            if self.found_primes.iter().all(|prime| num % prime != 0) {
                self.found_primes.push(num);
                self.next_to_check = num + 1;
                return Some(num);
            }
        }
        unreachable!()
    }
}

fn greatest_prime_divisor(mut number: u64) -> u64 {
    for prime in PrimesIterator::new() {
        while number % prime == 0 {
            number /= prime;
        }
        if number <= 1 {
            return prime;
        }
    }
    unreachable!()
}

fn main() {
    let number = std::env::args().nth(1).expect("Number must be first argument");
    let number: u64 = number.parse().unwrap();
    println!("The greatest prime divisor of {} is {}", number, greatest_prime_divisor(number));
}

Result:

The greatest prime divisor of 600851475143 is 6857