Shared via Rust Playground

prime_list.rs

#![allow(dead_code, unused_variables)]

struct PrimeList {
    primes: Vec<i32>,
}

/// Basically the same as 
/// self.primes.iter().cloned().chain(self) on a PrimeList
struct PrimeIter<'a> {
    primes: &'a mut PrimeList,
    idx: usize,
}


impl<'a> Iterator for PrimeIter<'a> {
    type Item = i32;

    fn next(&mut self) -> Option<i32> {
        let val = self.primes.primes.get(self.idx).cloned();
        self.idx += 1;
        val.or_else(|| self.primes.next())
    }

    fn nth(&mut self, n: usize) -> Option<i32> {
        self.idx = n;
        if let Some(val) = self.primes.primes.get(n).cloned() {
            Some(val)
        } else {
            let diff = n - self.primes.primes.len();
            self.primes.nth(diff)
        }
    }
}

impl PrimeList {
    pub fn new() -> PrimeList {
        PrimeList { primes: vec![2] }
    }

    pub fn last_known(&self) -> i32 {
        self.primes.last().cloned().unwrap()
    }

    pub fn next_prime(&self) -> i32 {
        let last = self.last_known();
        (last + 1..).filter(|&n| self.check_prime(n)).next().unwrap()
    }

    pub fn prime_iter(&mut self) -> PrimeIter {
        PrimeIter {
            primes: self,
            idx: 0,
        }
    }

    fn is_prime(&mut self, p: i32) -> bool {
        let last = self.last_known();
        // Todo: bin_search
        if last * last < p {
            for _ in self.take_while(|&n| n * n <= p) {}
        }
        self.check_prime(p)
    }

    fn is_prime_alt(&mut self, p: i32) -> bool {
        // Todo: bin_search
        self.prime_iter().take_while(|&n| n * n <= p).all(|n| p % n != 0)
    }

    /// Assumes that all primes up to sqrt(p) are known
    fn check_prime(&self, p: i32) -> bool {
        let last = self.last_known();
        assert!(last * last >= p);
        self.primes.iter().take_while(|&n| n * n <= p).all(|n| p % n != 0)
    }
}

impl Iterator for PrimeList {
    type Item = i32;

    fn next(&mut self) -> Option<i32> {
        let p = self.next_prime();
        self.primes.push(p);
        Some(p)
    }
}

fn main() {
    let mut primes = PrimeList::new();
    // for _ in (&mut primes).take(100) {}
    println!("{}", primes.is_prime_alt(1451));
    println!("{:?}", primes.primes);
}