Skip to content

Instantly share code, notes, and snippets.

Created April 13, 2016 04:39
Show Gist options
  • Save anonymous/a1f2f5665541fec2a97c8c7a2ea74261 to your computer and use it in GitHub Desktop.
Save anonymous/a1f2f5665541fec2a97c8c7a2ea74261 to your computer and use it in GitHub Desktop.
Shared via Rust Playground
#![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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment