4 releases
0.1.3 | Jul 16, 2023 |
---|---|
0.1.2 | Jul 12, 2023 |
0.1.1 | Jul 12, 2023 |
0.1.0 | Jul 11, 2023 |
#1091 in Algorithms
18KB
278 lines
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 fromsource
(s).
Both source
(s) and sieve
(s) implement Iterator<Item = u64>
.
This crate provides the following sieves:
UnfaithfulSieve
: Non-recursiveIterator
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.