Struct primal::StreamingSieve [−] [src]

```pub struct StreamingSieve {
// some fields omitted
}```

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

Methods

`impl StreamingSieve`

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

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

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