# Crate lazy_prime_sieve

source ·## Expand description

`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

- Module providing sieves for generating primes.
- Module providing sources of integers to sample primes from.

## Functions

- Returns an Iterator of prime numbers.