lazy-prime-sieve

Lazy Sieve of Eratosthenes for infinitely generating primes lazily in Rust.

Usage

lazy-prime-sieve is a library crate. You may add it to your Cargo.toml as follows:

[dependencies]
lazy-prime-sieve = "0.1.3"

lazy-prime-sieve provides iterators for infinitely generating primes. This crate provides a convenience method ::primes() which returns the most efficient iterator (in this crate) for generating primes.

use lazy_prime_sieve::primes;

for i in primes().take(10) {
    println!("{i}");
}

Design

This crate provides two types of abstractions: sieve(s) and source(s).

• source(s) represent infinite sources of integers from which we sample primes.
• sieve(s) sample primes from source(s).

Both source(s) and sieve(s) implement Iterator<Item = u64>.

This crate provides the following sieves:

• UnfaithfulSieve: Non-recursive Iterator based alternative to classic Haskell lazy recursive prime sieve:

  primes = sieve [2..]
  sieve (p : xs) = p : sieve [x | x <− xs, x ‘mod‘ p > 0]
  

• TrialDivsionSieve: The modulus-based memoized approach of generating primes that we all know and love.
• GenuineSieve: Priority Queue based solution, true to the original Sieve of Eratosthenes algorithm.

This crate provides the following sources:

• integer_candidates(): Returns an iterator which yields the sequence 2, 3, 4, 5, 6, 7, …
• odds_with_2(): Returns an iterator which yields the sequence 2, 3, 5, 7, 9, …
• SpinWheel::default(): Iterator of monotonically increasing integers which are not multiples of 2, 3, 5 and 7.

Mostly, we initialize a sieve with a source and start generating primes:

use lazy_prime_sieve::{sieve::TrialDivisionSieve, source::odds_with_2};

// print the first 10 primes
TrialDivisionSieve::with_source(odds_with_2())
  .take(10)
  .for_each(|x| println!("{x}"));

However, some sources start from a high number. So we need to chain the initial primes:

use lazy_prime_sieve::{source::SpinWheel, sieve::GenuineSieve};

// starts from 11
let source = SpinWheel::default();

// print the first 10 primes
[2, 3, 5, 7]
    .iter()
    .cloned()
    .chain(GenuineSieve::with_source(source))
    .take(10)
    .for_each(|x| println!("{x}"));

Refer to the documentation for further details.

Benchmarks

This benchmark shows the time taken by the different (source, sieve) combinations (fmt: "{sieve}_with_{source}") in this crate to generate a certain number of primes. The x-axis shows the number of primes generated, while the y-axis shows the time taken.

The fastest combination is GenuineSieve with SpinWheel::default(). This is the combination used by lazy_prime_sieve::primes().

See the generated benchmark report here.

These benchmarks were run on an AMD Ryzen 7 x86_64 machine in WSL with 8 GB RAM allocated to WSL.

References

This crate heavily draws from the paper The Genuine Sieve of Eratosthenes. This repository attempts to provide non-recursive lazy Rust iterator based alternatives to the Haskell lazy list + recursion based methods proposed in the paper.

License

lazy-prime-sieve is licensed under the MIT License. See License for more details.