Over the past few weeks I’ve been working on improving my
slow_primes
library, culminating in needing rename and the 0.2
release of primal
, a Rust crate for computing properties of prime
numbers with stateoftheart algorithms, while still
maintaining an idiomatic and easytouse interface.
My computer takes a quarter of a second and less than 3MB of RAM to tell me that there 50,847,534 primes below 1 billion:
1
2
3
4
5
6
extern crate primal;
fn main() {
println!("there are {} primes below 1 billion",
primal::StreamingSieve::prime_pi(1_000_000_000));
}
Some of the first programming I did was Project Euler: a site that has little mathematical problems designed to be solved with the assistance of a computer. Beyond just the challenge of solving the problem, there’s the challenge of writing code to go as fast as possible: Project Euler will always hold a little place in my heart for making me learn a lot about writing fast code. That’s where I first tried to write fast prime sieves: I recall being pretty happy when I could sieve up to a “big” number like 1 million quickly; now I’m pretty happy that I can sieve up to 1 billion in (probably) less time, and certainly less memory.
Migrating from slow_primes
/primal
0.1
 rename
slow_primes
toprimal
or bump the version in yourCargo.toml
,  replace
Primes
withSieve
:Primes::sieve(100)
→Sieve::new(100)
,  call
primes_from
instead ofprimes()
:sieve.primes()
→sieve.primes_from(0)
,  revel in the improved sieving performance.
Highlights
primal
is pretty great, if I do say so myself:
 the documentation is complete: every function has some text
describing it, all have explicit examples (except
Sieve::new
), and there’s a nice introductory walkthrough tackling three classes of problems.  it includes a highly optimised segmented, wheel sieve:
Sieve
. It is essentially a Rust port of Kim Walisch’s awesome primesieve, which is apparently the fastest sieve in the world. The version inprimal
is really fast, certainly the fastest sieve I can find in Rust, but there’s still room to improve: the Rust version is currently around 520% slower than primesieve (singlethreaded), and lacks some of the fancier features that it adds on top. 
there’s some reasonably deep mathematics:
estimate_nth_prime(n)
andestimate_prime_pi(k)
provide fast (O(1)) but precise bounds for the nth prime, and the number of primes below k:estimate_prime_pi(1_000_000_000)
returns a lowerbound of 50,785,736 (0.12% below the true value) and an upperbound of 50,865,514 (0.04% above),estimate_nth_prime(50_847_535)
returns 999,873,297 and 1,000,273,162, which are 0.01% below and 0.03% above (respectively) the true value of 1,000,000,007.
However, my favourite feature is Primes
: which is an fast
lazy iterator over all primes, with no upperbound (other than integer
size). In a flash of inspiration, I realised it would be possible to
do this reasonably efficiently with a simple wrapper around the core
sieve. It can be used a bit like:
1
2
3
4
5
6
extern crate primal;
fn main() {
println!("the 50,847,535th prime is {}",
primal::Primes::all().nth(50_847_535  1).unwrap());
}
It’s not the most efficient way to get the nth prime, but it still
only takes 0.9 0.52 seconds^{0} to print 1,000,000,007. (A better way is
StreamingSieve::nth_prime
, which takes ~0.22s for the
same task.)
 users
 /r/rust

I realised the original implementation was inefficient, and using far more memory than necessary: fixing that made a huge difference. ↩