### 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 |

#**751** in Algorithms

**21** downloads per month

**MIT**license

18KB

278 lines

`lazy-prime-sieve`

`lazy-prime-sieve`

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

## Usage

is a library crate. You may add it to your `lazy-prime-sieve`

as
follows:`Cargo.toml`

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

provides iterators for infinitely generating primes. This
crate provides a convenience method `lazy-prime-sieve`

which returns the most
efficient iterator (in this crate) for generating primes.` ::`primes

`(`

`)`

`use` `lazy_prime_sieve``::`primes`;`
`for` i `in` `primes``(``)``.``take``(``10``)` `{`
`println!``(``"``{i}``"``)``;`
`}`

## Design

This crate provides two types of abstractions:

(s) and `sieve`

(s).`source`

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

(s) sample primes from`sieve`

(s).`source`

Both

(s) and `source`

(s) implement `sieve`

.`Iterator``<`Item = `u64``>`

This crate provides the following sieves:

: Non-recursive`UnfaithfulSieve`

based alternative to classic Haskell lazy recursive prime sieve:`Iterator``primes``=`sieve [`2``..`] sieve (p`:`xs)`=`p`:`sieve [x`|`x`<`− xs`,`x ‘mod‘ p`>``0`]

: The modulus-based memoized approach of generating primes that we all know and love.`TrialDivsionSieve`

: Priority Queue based solution, true to the original Sieve of Eratosthenes algorithm.`GenuineSieve`

This crate provides the following sources:

: Returns an iterator which yields the sequence 2, 3, 4, 5, 6, 7, …`integer_candidates``(``)`

: Returns an iterator which yields the sequence 2, 3, 5, 7, 9, …`odds_with_2``(``)`

: Iterator of monotonically increasing integers which are not multiples of 2, 3, 5 and 7.`SpinWheel`default`::``(``)`

Mostly, we initialize a

with a `sieve`

and start generating primes:`source`

`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

combinations (fmt: `(`source`,` sieve`)`

) in this crate to generate a
certain number of primes. The `"`{sieve}_with_{source}`"`

shows the number of primes generated,
while the `x-axis`

shows the time taken.`y-axis`

The fastest combination is

with `GenuineSieve`

. This is
the combination used by `SpinWheel ::`default

`(`

`)`

`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

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