lazy-prime-sieve
Lazy Sieve of Eratosthenes for infinitely generating primes lazily in Rust.
lazy-prime-sieve is a library crate. You may add it to your Cargo.toml as
follows:
toml
[dependencies]
lazy-prime-sieve = "0.1.2"
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.
```rust use lazyprimesieve::primes;
for i in primes().take(10) { println!("{i}"); } ```
This crates two kinds 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:
haskell
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 source:
- 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:
```rust use lazyprimesieve::{sieve::TrialDivisionSieve, source::oddswith2};
// print the first 10 primes TrialDivisionSieve::withsource(oddswith2()) .take(10) .foreach(|x| println!("{x}")); ```
However some sources start from a high number. So we need to chain the initial primes:
```rust use lazyprimesieve::{source::SpinWheel, sieve::GenuineSieve};
// starts from 11 let source = SpinWheel::default();
// print the first 10 primes [2, 3, 5, 7] .iter() .cloned() .chain(GenuineSieve::withsource(source)) .take(10) .foreach(|x| println!("{x}")); ```
Refer to the documentation for further details.
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 amount of time taken.
The fastest combination is GenuineSieve with SpinWheel::default(). This is
the combination used by lazy_prime_sieve::primes().
These benchmarks were run on an AMD Ryzen 7 x86_64 machine in WSL with 8 GB RAM allocated to WSL.
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.
lazy-prime-sieve is licensed under the MIT License. See
License
for more details.