rk_primes/
cache.rs

1use std::{cell::RefCell, mem};
2
3use super::UNDER_100000;
4
5/// Returns true if none of the known primes divides n (other than n itself).
6///
7/// Prerequisite: The slice of known primes is sorted.
8fn is_prime_known(n: u32, known: &[u32]) -> bool {
9    !known.iter().take_while(|&&p| p < n).any(|p| n % p == 0)
10}
11
12pub struct Primes<'a> {
13    cache: &'a Cache,
14    next: u32,
15}
16
17impl Iterator for Primes<'_> {
18    type Item = u32;
19
20    fn next(&mut self) -> Option<Self::Item> {
21        let next = if self.next == 2 {
22            3
23        } else {
24            let mut next = self.next;
25            while !self.cache.is_prime(next) {
26                next += 2;
27            }
28            next
29        };
30        Some(mem::replace(&mut self.next, next))
31    }
32}
33
34#[derive(Default)]
35pub struct Cache {
36    known: RefCell<Vec<u32>>,
37}
38
39impl Cache {
40    fn extend_past(&self, n: u32) {
41        let mut known = self.known.borrow_mut();
42        if known.is_empty() {
43            known.extend_from_slice(&UNDER_100000);
44        }
45        let last = known[known.len() - 1];
46        if last < n {
47            let limit = n * 2; // Arbitrary.
48            for candidate in (last..limit).step_by(2) {
49                if is_prime_known(candidate, &known) {
50                    known.push(candidate);
51                }
52            }
53        }
54    }
55
56    pub fn is_prime(&self, n: u32) -> bool {
57        self.extend_past(n);
58        self.known.borrow().binary_search(&n).is_ok()
59    }
60
61    #[must_use]
62    pub fn new(known: &[u32]) -> Cache {
63        Cache {
64            known: RefCell::new(known.to_vec()),
65        }
66    }
67
68    pub fn primes(&self) -> Primes {
69        Primes {
70            cache: self,
71            next: 2,
72        }
73    }
74}
75
76#[cfg(test)]
77mod tests {
78    use crate::UNDER_1000;
79
80    use super::*;
81
82    #[ignore = "slow"]
83    #[test]
84    fn test_cache_is_prime() {
85        let cache = Cache::new(&UNDER_1000);
86        for n in 0..100_000 {
87            assert_eq!(cache.is_prime(n), UNDER_100000.contains(&n));
88        }
89    }
90}
rk_primes/cache.rs

rk_primes/
cache.rs
