Crate lazy_prime_sieve

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.

Modules

sieve

Module providing sieves for generating primes.

source

Module providing sources of integers to sample primes from.

Functions

primes

Returns an Iterator of prime numbers.