haar_lib/math/prime_test/
mod.rs

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

haar_lib/math/prime_test/
mod.rs
