58 lines
1.5 KiB
Rust
58 lines
1.5 KiB
Rust
struct PrimesIterator {
|
|
/// MUST contain all primes up to its max value!
|
|
known_primes: Vec<u128>,
|
|
}
|
|
|
|
impl PrimesIterator {
|
|
fn new() -> Self {
|
|
PrimesIterator {
|
|
known_primes: Vec::new(),
|
|
}
|
|
}
|
|
|
|
/// Checks if a value is prime based on the values within the known_primes vector
|
|
fn is_known_prime(&self, candidate: u128) -> bool {
|
|
for prime in self.known_primes.iter() {
|
|
if *prime > (candidate + 1) / 2 {
|
|
// We have exhausted all divisor candidates.
|
|
return true;
|
|
}
|
|
|
|
if candidate % *prime == 0 {
|
|
return false;
|
|
}
|
|
}
|
|
true
|
|
}
|
|
}
|
|
|
|
impl Iterator for PrimesIterator {
|
|
type Item = u128;
|
|
|
|
fn next(&mut self) -> Option<Self::Item> {
|
|
if self.known_primes.is_empty() {
|
|
self.known_primes.push(2);
|
|
Some(2)
|
|
} else if self.known_primes.len() == 1 {
|
|
self.known_primes.push(3);
|
|
Some(3)
|
|
} else {
|
|
let mut last_checked = *self.known_primes.last().unwrap() + 2;
|
|
while !self.is_known_prime(last_checked) {
|
|
last_checked += 2;
|
|
}
|
|
self.known_primes.push(last_checked);
|
|
Some(last_checked)
|
|
}
|
|
}
|
|
}
|
|
|
|
fn main() {
|
|
let sum: u128 = PrimesIterator::new()
|
|
.take_while(|v| *v < 2_000_000)
|
|
.enumerate()
|
|
.map(|(i, v)| { if i % 1000 == 0 { println!("{}", v); }; v })
|
|
.sum();
|
|
println!("{}", sum);
|
|
}
|