use super::PrimalityTest;
use num_traits::{PrimInt, ToPrimitive, FromPrimitive};
#[derive(Default)]
pub struct SieveAlgorithm;
impl<N: PrimInt + ToPrimitive + FromPrimitive> PrimalityTest<N> for SieveAlgorithm {
fn name(&self) -> &'static str {
"Sieve of Eratosthenes"
}
fn is_prime(&self, n: N) -> bool {
is_prime_sieve(n)
}
}
pub fn is_prime_sieve<N: PrimInt + ToPrimitive + FromPrimitive>(n: N) -> bool {
let zero = N::zero();
let one = N::one();
let two = N::from_u64(2).unwrap();
if n <= one {
return false;
}
if n == two {
return true;
}
if n % two == zero {
return false;
}
let n_f64 = n.to_f64().unwrap();
let limit = N::from_u64(n_f64.sqrt() as u64 + 1).unwrap();
let mut i = N::from_u64(3).unwrap();
while i <= limit {
if n % i == zero {
return false;
}
i = i + two;
}
true
}