Struct primal::Sieve [] [src]

pub struct Sieve {
    // some fields omitted

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.


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



impl Sieve

fn new(limit: usize) -> Sieve

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

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.


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

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

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

Determine if n is a prime number.


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


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);

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

Count the number of primes upto and including n.


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


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);

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.


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 * 97 * 97 * 991 * 991),
           Err((991 * 991, vec![(2, 1), (3, 1), (97, 2)])));

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

Compute pn, the n prime number, 1-indexed (i.e. p1 = 2, p2 = 3).


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())).


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);

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

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.


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


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

Derived Implementations

impl Debug for Sieve

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