1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#[derive(Debug)]
pub struct PrimeSieve(pub Vec<u32>);
impl PrimeSieve {
pub fn new(below: u32) -> Self {
let mut sieve = vec![true; below as usize];
let mut primes = Vec::new();
sieve.splice(0..2, [false; 2].iter().cloned());
for idx in 0..sieve.len() {
let candidate = sieve[idx];
if candidate == true {
let mut iter = sieve.iter_mut();
if iter.nth((idx * idx) - 1).is_some() {
for b in iter.step_by(idx) {
*b = false;
}
}
primes.push(idx as u32);
}
}
PrimeSieve(primes)
}
}
#[derive(Debug)]
pub struct PrimeGen {
below: Option<u32>,
counter: Option<u32>,
primes: Vec<u32>,
}
impl PrimeGen {
pub fn new(below: Option<u32>) -> Self {
Self {
below,
counter: None,
primes: Vec::new(),
}
}
}
impl Iterator for PrimeGen {
type Item = u32;
fn next(&mut self) -> Option<u32> {
let next_prime = if let Some(counter) = self.counter {
let mut candidate = counter + 2;
while self
.primes
.iter()
.filter(|&x| *x <= ((candidate as f32).sqrt() as u32))
.any(|&x| candidate % x == 0)
{
candidate += 2
}
self.counter = Some(candidate);
self.primes.push(candidate);
candidate
} else {
self.counter = Some(1);
self.primes.push(2);
2
};
match self.below {
Some(num) if num <= next_prime => None,
_ => Some(next_prime),
}
}
}