# Crate primal [−] [src]

`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 the author's laptop (i7-3517U).

# Using this library

Just add the following to your `Cargo.toml`

:

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

# Example

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

`Primes`

is flexible at the cost of performance, so if we wish to
optimise we could instead explicitly sieve and then find the
appropriate prime. Unfortunately, `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 the 10001st prime. We could
guess that, say, 10^{8} will be large enough and use that,
but that's probably a huge overestimate. 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`

.

// find our upper bound let (_lo, hi) = primal::estimate_nth_prime(10001); // find the primes up to this upper bound let sieve = primal::Sieve::new(hi as usize); let p = sieve.primes_from(0).nth(10001 - 1).unwrap(); println!("The 10001st prime is {}", p); // 104743

## Structs

Primes |
An iterator over all primes. |

Sieve |
A heavily optimised prime sieve. |

StreamingSieve |
A heavily optimised prime sieve. |

## Functions

as_perfect_power |
Returns integers |

as_prime_power |
Return |

estimate_nth_prime |
Gives estimated bounds for `n` th prime number,
1-indexed (i.e. p = 2, _{1}p = 3)._{2} |

estimate_prime_pi |
Returns estimated bounds for π( |

is_prime |
Test if |