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