## Expand description

`primal`

puts raw power into prime numbers.

This crates includes

- optimised prime sieves
- checking for primality
- enumerating primes
- factorising numbers
- estimating upper and lower bounds for π(
*n*) (the number of primes below*n*) and*p*(the_{k}*k*th prime)

This uses a state-of-the-art cache-friendly Sieve of Eratosthenes to enumerate the primes up to some fixed bound (in a memory efficient manner), and then allows this cached information to be used for things like enumerating and counting primes.

`primal`

takes around 2.8 seconds and less than 3MB of RAM to
count the exact number of primes below 10^{10} (455052511)
on my laptop (i7-3517U).

## Using this library

Just add the following to your `Cargo.toml`

:

```
[dependencies]
primal = "0.2"
```

## Examples

### “Indexing” Primes

Let’s find the 10001st prime. The easiest way is to enumerate the primes, and find the 10001st:

```
// (.nth is zero indexed.)
let p = primal::Primes::all().nth(10001 - 1).unwrap();
println!("The 10001st prime is {}", p); // 104743
```

This takes around 400 microseconds on my computer, which seems
nice and quick, but, `Primes`

is flexible at the cost of
performance: we can make it faster. The `StreamingSieve`

type
offers a specialised `nth_prime`

function:

```
let p = primal::StreamingSieve::nth_prime(10001);
println!("The 10001st prime is {}", p); // 104743
```

This runs in only 10 microseconds! `StreamingSieve`

is extremely
efficient and uses very little memory. It is the best way to solve
this task with `primal`

.

Since that was so easy, let’s now make the problem bigger and harder: find the sum of the 100,000th, 200,000th, 300,000th, …, 10,000,000th primes (100 in total).

We could call `StreamingSieve::nth_prime`

repeatedly:

```
// the primes we want to find
let ns = (1..100 + 1).map(|x| x * 100_000).collect::<Vec<_>>();
// search and sum them up
let sum = ns.iter()
.map(|n| primal::StreamingSieve::nth_prime(*n))
.fold(0, |a, b| a + b);
println!("the sum is {}", sum);
```

This takes around 1.6s seconds to print `the sum is 8795091674`

;
not so speedy. Each call to `nth_prime`

is individually fast (400
microseconds for 100,000 to 40 milliseconds for 10,000,000) but
they add up to something bad. Every one is starting from the start
and redoing work that previous calls have done… wouldn’t it be
nice if we could just do the computation for 10,000,000 and reuse
that for the smaller ones?

The `Sieve`

type is a wrapper around `StreamingSieve`

that
caches information, allowing repeated queries to be answered
efficiently.

There’s one hitch: `Sieve`

requires a limit to know how far to
sieve: we need some way to find an upper bound to be guaranteed to
be at least as large as all our primes. We could guess that, say,
10^{10} will be large enough and use that, but that’s a
huge overestimate (spoilers: the 10,000,000th prime is around
2×10^{8}). We could also try filtering with
exponentially larger upper bounds until we find one that works
(e.g. doubling each time), or, we could just take a shortcut and
use deeper mathematics via
`estimate_nth_prime`

.

```
// the primes we want to find
let ns = (1..100 + 1).map(|x| x * 100_000).collect::<Vec<_>>();
// find our upper bound
let (_lo, hi) = primal::estimate_nth_prime(10_000_000);
// find the primes up to this upper bound
let sieve = primal::Sieve::new(hi as usize);
// now we can efficiently sum them up
let sum = ns.iter()
.map(|n| sieve.nth_prime(*n))
.fold(0, |a, b| a + b);
println!("the sum is {}", sum);
```

This takes around 40 milliseconds, and gives the same output: much better!

(By the way, the version using 10^{10} as the bound
instead of the more accurate estimate still only takes ~3
seconds.)

### Counting Primes

Another problem: count the number of primes below 1 million. This
is evaluating the prime-counting function
π,
i.e. π(10^{6}).

As above, there’s a few ways to attack this: the iterator, and the sieves.

```
const LIMIT: usize = 1_000_000;
// iterator
let count = primal::Primes::all().take_while(|p| *p < LIMIT).count();
println!("there are {} primes below 1 million", count); // 78498
// sieves
let sieve = primal::Sieve::new(LIMIT);
let count = sieve.prime_pi(LIMIT);
println!("there are {} primes below 1 million", count);
let count = primal::StreamingSieve::prime_pi(LIMIT);
println!("there are {} primes below 1 million", count);
```

`StreamingSieve`

is fastest (380 microseconds) followed by `Sieve`

(400) with `Primes`

bringing up the rear at 1300 microseconds. Of
course, repeated queries will be faster with `Sieve`

than with
`StreamingSieve`

, but that flexibility comes at the cost of extra
memory use.

If an approximation is all that is required, `estimate_prime_pi`

provides close upper and lower bounds:

```
let (lo, hi) = primal::estimate_prime_pi(1_000_000);
println!("there are between {} and {} primes below 1 million", lo, hi);
// 78380, 78573
```

### Searching Primes

Now for something where `Primes`

might be useful: find the first
prime where the binary expansion (not including trailing zeros)
ends like `00..001`

with at least 27 zeros. This condition is
checked by:

```
fn check(p: usize) -> bool {
p > 1 && (p / 2).trailing_zeros() >= 27
}
```

I have no idea how large the prime might be: I know it’s
guaranteed to be at *least* 2^{27 + 1} + 1, but not an
upper limit.

The `Primes`

iterator works perfectly for this:

```
let p = primal::Primes::all().find(|p| check(*p)).unwrap();
println!("the prime is {}", p);
```

It takes about 3.1 seconds for my computer to spit out 3,221,225,473.

Using a sieve is a little trickier: one approach is to start with
some estimated upper bound (like double the absolute lower bound),
look for a valid prime. If one isn’t found, double the upper bound
and start again. The `primes_from`

method allows for saving a
little bit of work: we can start iterating from an arbitrary point
in the sequence, such as the lower bound.

```
let p;
let mut lower_bound = 1 << (27 + 1);
loop {
// our upper bound is double the lower bound
let sieve = primal::Sieve::new(lower_bound * 2);
if let Some(p_) = sieve.primes_from(lower_bound).find(|p| check(*p)) {
p = p_;
break
}
lower_bound *= 2;
}
println!("the prime is {}", p);
```

This takes around 3.5 seconds to print the same number. Slower than the iterator!

I was just using this silly condition as an example of something
that doesn’t have an obvious upper bound, rather than a problem
that is hard to do fast. There’s a much faster way to tackle it,
by inverting the problem: construct numbers that satisfy `check`

,
and check the primality of those.

The numbers that satisfy `check`

are `k * (1 << (27 + 1)) + 1`

for
`k >= 1`

, so the only hard bit is testing primality. Fortunately,
`primal`

offers the `is_prime`

function which is an efficient way
to do primality tests, even of very large numbers.

```
let mut p = 0;
for k in 1.. {
p = k * (1 << (27 + 1)) + 1;
if primal::is_prime(p) { break }
}
println!("the prime is {}", p);
```

This takes 6 *micro*seconds: more than 500,000×
faster than the iterator!

## Structs

An iterator over all primes.

A heavily optimised prime sieve.

An iterator over the primes stored in a `Sieve`

instance.

A heavily optimised prime sieve.

## Functions

Returns integers `(y, k)`

such that `x = y^k`

with `k`

maximised
(other than for `x = 0, 1`

, in which case `y = x`

, `k = 1`

).

Return `Some((p, k))`

if `x = p^k`

for some prime `p`

and `k >= 1`

(that is, including when `x`

is itself a prime).

Gives estimated bounds for *p _{n}*, the

`n`

th prime number,
1-indexed (i.e. *p*= 2,

_{1}*p*= 3).

_{2}Returns estimated bounds for π(*n*), the number of primes less
than or equal to `n`

.

Test if `n`

is prime, using the deterministic version of the
Miller-Rabin test.