haar_lib/math/primality/
mod.rs

1//! 素数判定
2
3pub mod eratosthenes;
4pub mod linear_sieve;
5pub mod miller_rabin;
6pub mod segmented;
7
8/// 素数判定
9pub trait PrimalityTest<T> {
10    /// `value`が素数ならば`true`を返す。
11    fn is_prime(&self, value: T) -> bool;
12}
13
14#[cfg(test)]
15mod tests {
16    use crate::timer;
17
18    use super::{eratosthenes::*, linear_sieve::LinearSieve, miller_rabin::*, PrimalityTest};
19
20    #[test]
21    fn test_eratosthenes() {
22        let n = 100;
23        let sieve = EratosthenesSieve::new(n);
24
25        let primes = (1..=n).filter(|&i| sieve.is_prime(i)).collect::<Vec<_>>();
26
27        assert_eq!(
28            primes,
29            [
30                2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
31                83, 89, 97
32            ]
33        );
34    }
35
36    #[test]
37    fn test_linear_sieve() {
38        let n = 10000;
39        let sieve1 = EratosthenesSieve::new(n);
40        let sieve2 = LinearSieve::new(n);
41
42        for i in 1..=n {
43            assert_eq!(sieve1.is_prime(i), sieve2.is_prime(i));
44        }
45    }
46
47    #[test]
48    fn test_miller_rabin() {
49        let n = 1000;
50        let sieve = EratosthenesSieve::new(n);
51
52        let primes = (1..=n).filter(|&i| sieve.is_prime(i)).collect::<Vec<_>>();
53
54        assert_eq!(
55            (1..=n)
56                .filter(|&i| MillerRabin.is_prime(i as u64))
57                .collect::<Vec<_>>(),
58            primes
59        );
60    }
61
62    #[test]
63    fn benchmark() {
64        let ns = [
65            1, 10, 100, 1_000, 10_000, 100_000, 1_000_000, 10_000_000,
66            //100_000_000,
67        ];
68
69        eprintln!("Sieve of Eratosthenes");
70        for &n in &ns {
71            timer!(n, {
72                let _ = EratosthenesSieve::new(n);
73            })
74        }
75
76        eprintln!("Linear sieve");
77        for &n in &ns {
78            timer!(n, {
79                let _ = LinearSieve::new(n);
80            })
81        }
82    }
83}
haar_lib/math/primality/mod.rs

haar_lib/math/primality/
mod.rs
