haar_lib/math/prime_test/
mod.rs

1//! 素数判定
2
3pub mod eratosthenes;
4pub mod miller_rabin;
5pub mod segmented;
6
7/// 素数判定
8pub trait CheckPrime<T> {
9    /// `value`が素数ならば`true`を返す。
10    fn is_prime(&self, value: T) -> bool;
11}
12
13#[cfg(test)]
14mod tests {
15    use super::{eratosthenes::*, miller_rabin::*, CheckPrime};
16
17    #[test]
18    fn test_eratosthenes() {
19        let n = 100;
20        let sieve = EratosthenesSieve::new(n);
21
22        let primes = (1..=n).filter(|&i| sieve.is_prime(i)).collect::<Vec<_>>();
23
24        assert_eq!(
25            primes,
26            [
27                2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
28                83, 89, 97
29            ]
30        );
31    }
32
33    #[test]
34    fn test_miller_rabin() {
35        let n = 1000;
36        let sieve = EratosthenesSieve::new(n);
37
38        let primes = (1..=n).filter(|&i| sieve.is_prime(i)).collect::<Vec<_>>();
39
40        assert_eq!(
41            (1..=n)
42                .filter(|&i| MillerRabin.is_prime(i as u64))
43                .collect::<Vec<_>>(),
44            primes
45        );
46    }
47}
haar_lib/math/prime_test/mod.rs

haar_lib/math/prime_test/
mod.rs
