Struct primal_slowsieve::Primes

pub struct Primes { /* fields omitted */ }

Stores information about primes up to some limit.

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

Methods

impl Primes

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.

fn upper_bound(&self) -> usize

The largest number stored.

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.

fn primes<'a>(&'a self) -> PrimeIterator<'a>

Iterator over the primes stored in this map.

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.

Trait Implementations

impl Debug for Primes

fn fmt(&self, __arg_0: &mut Formatter) -> Result

Formats the value using the given formatter.