Struct comlib_math::PrimeSieve

pub struct PrimeSieve(_);

Sieve of Eratosthenes.

Sieve of Eratosthenes can be quickly used to determine whether a number is a prime and to find out its prime factorization.

Time complexity

The construction of the sieve takes O(n log log n) time. After this checking whether a number is a prime takes O(1) time and finding the factorization takes O(log n) time.

Implementation details

Internally the sieve stores for each index the largest prime which divides the corresponding value. For 0 and 1 the sieve stores 0 as neither is divisible by any prime.

Implementations

impl PrimeSieve

pub fn new(n: u64) -> Self

Constructs a new PrimeSieve.

Takes O(n log log n) time.

pub fn is_prime(&self, n: u64) -> bool

Checks whether the given number is a prime.

pub fn factorize(&self, n: u64) -> Vec<(u64, usize)>

Factorizes the given number into its prime factors.

Returns the factors as pairs indicating the prime and the number of times its present in the factorization. The factorization is ordered in increasing order by the prime.

pub fn into_inner(self) -> Vec<u64>

Turns the sieve into raw vector telling the largest prime divisor for each index.