Shared via Rust Playground

playground.rs

#![allow(dead_code, unused_variables)]

struct PrimeList {
    primes: Vec<i64>,
}

/// 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 = i64;

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

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

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

    pub fn next_prime(&self) -> i64 {
        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: i64) -> bool {
        match self.primes.binary_search(&p) {
          Ok(_) => {println!("Cached {}",p);return true},
          Err(n) if n == self.primes.len() => {println!("{:?}:",n);}
          Err(n) => {println!("{:?}:{:?}",n,self.primes.len());}
        }
        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: i64) -> 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: i64) -> 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 = i64;

    fn next(&mut self) -> Option<i64> {
        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.is_prime(50));
    println!("{:?}", primes.primes);
    //println!("{:?}", primes.prime_iter().nth(10001));
    
}