Shared via Rust Playground

playground.rs

#![allow(dead_code, unused_variables)]

struct PrimeList {
    primes: Vec<i32>,
}

struct PrimeIter<'a> {
    primes: &'a mut PrimeList,
    has_cached: bool,
}

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()
    }

    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)
        //self.primes.iter().cloned().chain(self).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 nth(&mut self, n: usize) -> Option<i32> {
        self.primes.get(n).cloned()
    }
}

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