Struct primal::StreamingSieve

pub struct StreamingSieve { /* private fields */ }

A heavily optimised prime sieve.

This is a streaming segmented sieve, meaning it sieves numbers in intervals, extracting whatever it needs and discarding it. See Sieve for a wrapper that caches the information to allow for repeated queries, at the cost of O(limit) memory use.

This uses O(sqrt(limit)) memory, and is designed to be as cache-friendly as possible. StreamingSieve should be used for one-off calls, or simple linear iteration.

The design is heavily inspired/adopted from Kim Walisch’s primesieve, and has similar speed (around 5-20% slower).

Examples

let count = primal::StreamingSieve::prime_pi(123456);
println!("𝜋(123456) = {}", count);

Implementations

impl StreamingSieve

pub fn prime_pi(n: usize) -> usize

Count the number of primes upto and including n, that is, 𝜋, the prime counting function.

Examples

assert_eq!(primal::StreamingSieve::prime_pi(10), 4);
// the endpoint is included
assert_eq!(primal::StreamingSieve::prime_pi(11), 5);

assert_eq!(primal::StreamingSieve::prime_pi(100), 25);
assert_eq!(primal::StreamingSieve::prime_pi(1000), 168);

pub fn nth_prime(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

assert_eq!(primal::StreamingSieve::nth_prime(1_000), 7919);

Trait Implementations

impl Debug for StreamingSieve

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

Formats the value using the given formatter.