# 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.

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

## Methods

### `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.

# Examples

```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.

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

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

#### `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`.

# 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 * 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).

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

#### `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.

# Panics

If `n` is out of range (greater than `self.upper_bound()`), `prime_pi` 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);
}```