# prime-suspects



An O(sqrt(n))-time implementation of Eratosthenes' sieve in Rust, with an
additional implementation using segmented sieving to ensure O(sqrt(n)) memory
usage.

I also wrote a
[Ruby version](https://github.com/bright-star/prime-suspects/tree/master).

## try it

1. `cargo run --example simple_eratosthenes`
2. `cargo test` for different unit/documentation tests

## docs

1. `cargo doc --open`

## references

Shepmaster on Stack Overflow was beyond helpful in
[code review](http://codereview.stackexchange.com/questions/128545/writing-a-rustic-segmented-prime-number-sieve)
and in learning how to handle
[borrowing in parallel threads](http://stackoverflow.com/questions/37713367/why-does-this-variable-definition-imply-static-lifetime).

A list of other references I consulted along the way:

- http://research.cs.wisc.edu/techreports/1990/TR909.pdf
- https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_and_variants
- http://stackoverflow.com/questions/36221430/why-does-the-closure-for-take-while-take-its-argument-by-reference
- http://stackoverflow.com/questions/36988470/how-do-you-implement-an-iterator-whose-successor-depends-on-the-index-of-the-ter