Struct primal_slowsieve::Primes

pub struct Primes { /* private fields */ }

Stores information about primes up to some limit.

This uses at least limit / 16 + O(1) bytes of storage.

Implementations

impl Primes

pub fn sieve(limit: usize) -> Primes

Construct a Primes via a sieve up to at least limit.

This stores all primes less than limit (and possibly some more), allowing for very efficient iteration and primality testing below this, and guarantees that all numbers up to limit^2 can be factorised.

pub fn upper_bound(&self) -> usize

The largest number stored.

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

Check if n is prime, possibly failing if n is larger than the upper bound of this Primes instance.

pub fn primes(&self) -> PrimeIterator<'_>

Iterator over the primes stored in this map.

pub fn factor( &self, n: usize, ) -> Result<Vec<(usize, usize)>, (usize, Vec<(usize, usize)>)>

Factorise n into (prime, exponent) pairs.

Returns Err((leftover, partial factorisation)) if n cannot be fully factored, or if n is zero (leftover == 0). A number can not be completely factored if and only if the prime factors of n are too large for this sieve, that is, if there is

• a prime factor larger than U^2, or
• more than one prime factor between U and U^2

where U is the upper bound of the primes stored in this sieve.

Notably, any number between U and U^2 can always be fully factored, since these numbers are guaranteed to only have zero or one prime factors larger than U.

pub fn count_upto(&self, n: usize) -> usize

Count the primes upto and including n.

Panics

count_upto panics if n > self.upper_bound().

Trait Implementations

impl Debug for Primes

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.