Struct primal::Sieve

pub struct Sieve { /* private fields */ }

A heavily optimised prime sieve.

This stores information about primes up to some specified limit, allowing efficient queries of information about them. This caches the successive outputs of StreamingSieve and has very similar performance, modulo the differences in memory use: to cache the information Sieve uses approximately limit / 30 + O(sqrt(limit)) bytes of memory. Consider directly using StreamingSieve if repeated queries are unnecessary, since that uses only O(sqrt(limit)) bytes.

Examples

let sieve = primal::Sieve::new(10_000_000);
assert_eq!(sieve.prime_pi(123456), 11601);

assert!(sieve.is_prime(6395047));
assert!(!sieve.is_prime(6395048));

Implementations

impl Sieve

pub fn new(limit: usize) -> Sieve

Create a new instance, sieving out all the primes up to limit.

pub fn upper_bound(&self) -> usize

Return the largest number that this sieve knows about.

It will be at least as large as the number passed to new, but may be slightly larger.

Examples

let sieve = primal::Sieve::new(1000);

assert!(sieve.upper_bound() >= 1000);

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

Determine if n is a prime number.

Panics

If n is out of range (greater than self.upper_bound()), is_prime will panic.

Examples

let sieve = primal::Sieve::new(1000);

assert_eq!(sieve.is_prime(0), false);
assert_eq!(sieve.is_prime(1), false);
assert_eq!(sieve.is_prime(2), true);
assert_eq!(sieve.is_prime(3), true);
assert_eq!(sieve.is_prime(4), false);
assert_eq!(sieve.is_prime(5), true);

assert_eq!(sieve.is_prime(991), true);
assert_eq!(sieve.is_prime(993), false);
assert_eq!(sieve.is_prime(995), false);
assert_eq!(sieve.is_prime(997), true);
assert_eq!(sieve.is_prime(999), false);

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

Count the number of primes upto and including n.

Panics

If n is out of range (greater than self.upper_bound()), prime_pi will panic.

Examples

let sieve = primal::Sieve::new(1000);

assert_eq!(sieve.prime_pi(10), 4);
// the endpoint is included
assert_eq!(sieve.prime_pi(11), 5);

assert_eq!(sieve.prime_pi(100), 25);
assert_eq!(sieve.prime_pi(1000), 168);

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

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.

Examples

let sieve = primal::Sieve::new(100);

assert_eq!(sieve.factor(2), Ok(vec![(2, 1)]));
assert_eq!(sieve.factor(4), Ok(vec![(2, 2)]));
assert_eq!(sieve.factor(1 << 31), Ok(vec![(2, 31)]));

assert_eq!(sieve.factor(18), Ok(vec![(2, 1), (3, 2)]));

assert_eq!(sieve.factor(25 * 81), Ok(vec![(3, 4), (5, 2)]));

// "large" prime factors are OK, as long as there's only one
assert_eq!(sieve.factor(2 * 3 * 97 * 97 * 991),
           Ok(vec![(2, 1), (3, 1), (97, 2), (991, 1)]));

// too many large factors is problematic
assert_eq!(sieve.factor(991 * 991),
           Err((991 * 991, vec![])));
assert_eq!(sieve.factor(2 * 3 * 17 * 17 * 991 * 991),
           Err((991 * 991, vec![(2, 1), (3, 1), (17, 2)])));

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

Compute p_n, the n prime number, 1-indexed (i.e. p₁ = 2, p₂ = 3).

Panics

n must be larger than 0 and less than the total number of primes in this sieve (that is, self.prime_pi(self.upper_bound())).

Example

let (_, hi) = primal::estimate_nth_prime(1_000);

let sieve = primal::Sieve::new(hi as usize);

assert_eq!(sieve.nth_prime(10), 29);
assert_eq!(sieve.nth_prime(100), 541);
assert_eq!(sieve.nth_prime(1_000), 7919);

pub fn primes_from(&self, n: usize) -> SievePrimes<'_>

Return an iterator over the primes from n (inclusive) to the end of this sieve.

NB. it is not guaranteed that the end is the same as the limit passed to new: it may be larger. Consider using take_while if the limit must be exact.

Panics

If n is out of range (greater than self.upper_bound()), primes_from will panic.

Examples

let sieve = primal::Sieve::new(1_000);

// print the three digit primes
for p in sieve.primes_from(100).take_while(|x| *x < 1000) {
    println!("{}", p);
}

Trait Implementations

impl Debug for Sieve

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

Formats the value using the given formatter.