large_primes/primality/
standard.rs

1use num_bigint::BigUint;
2use num_traits::{ One, Zero };
3
4/// Performs the standard primality test by checking for prime factors from 2 to the square root of the given number.
5///
6/// This function checks whether the provided number is prime by testing for prime factors in the range from 2
7/// to the square root of the number (inclusive). It returns `true` if the number has no prime factors in that range,
8/// indicating that it is prime.
9///
10/// # Arguments
11///
12/// * `num` - A reference to a `BigUint` representing the number to test for primality.
13///
14/// # Returns
15///
16/// * `true` if `num` passes the standard primality test (has no prime factors from 2 to sqrt(num)).
17/// * `false` if `num` has a prime factor in the specified range or if `num` is less than or equal to 1.
18///   Note that the function returns `true` when `num` is 2, as it is the only even prime number.
19///
20/// # Examples
21///
22/// ```
23/// use num_bigint::BigUint;
24/// use large_primes::standard;
25/// 
26/// let prime_number = BigUint::from(19u32);
27/// assert!(standard(&prime_number));
28///
29/// let non_prime = BigUint::from(15u32);
30/// assert!(!standard(&non_prime));
31/// ```
32pub fn standard(num: &BigUint) -> bool {
33    // Standard test for prime factors from 2 to sqrt(num)+1
34    if *num <= BigUint::one() {
35        return false;
36    }
37    if *num == BigUint::from(2u32) {
38        return true;
39    }
40
41    let sqrt_num = num.sqrt() + BigUint::one();
42
43    let mut factor = BigUint::from(2u32);
44    while &factor <= &sqrt_num {
45        if num % &factor == BigUint::zero() {
46            return false;
47        }
48        factor += BigUint::one();
49    }
50
51    true
52}
53
54#[cfg(test)]
55mod tests {
56    use super::*;
57
58    #[test]
59    fn edge_cases() {
60        // Test case 0: False
61        assert_eq!(standard(&BigUint::zero()), false);
62
63        // Test case 1: False
64        assert_eq!(standard(&BigUint::one()), false);
65
66        // Test case 2: True
67        assert_eq!(standard(&BigUint::from(2u32)), true);
68
69        // Test case 3: True
70        assert_eq!(standard(&BigUint::from(3u32)), true);
71
72        // Test case 4: False
73        assert_eq!(standard(&BigUint::from(4u32)), false);
74    }
75
76    #[test]
77    fn large_primes() {
78        let primes = [
79            "871603259",
80            "98762051",
81            "1000000007",
82            "123575321",
83            "193818613",
84            "444444443",
85            "999999937",
86            "1000000000039",
87            "9999999929",
88        ];
89
90        for prime in primes {
91            let prime = BigUint::parse_bytes(prime.as_bytes(), 10).unwrap();
92            assert_eq!(standard(&prime), true);
93        }
94    }
95
96    #[test]
97    fn large_composites() {
98        let primes = ["914491", "15959", "767857", "14293", "680123", "617237"];
99
100        for i in 0..primes.len() {
101            for j in 0..primes.len() {
102                if i == j {
103                    continue;
104                }
105                let composite =
106                    BigUint::parse_bytes(primes[i].as_bytes(), 10).unwrap() *
107                    BigUint::parse_bytes(primes[j].as_bytes(), 10).unwrap();
108                assert_eq!(standard(&composite), false);
109            }
110        }
111    }
112}
large_primes/primality/standard.rs

large_primes/primality/
standard.rs
