# Crate slow_primes [−] [src]

Simplistic and relatively unoptimised handling of basic tasks around primes:

• checking for primality
• enumerating primes
• factorising numbers
• estimating upper and lower bounds for π(n) (the number of primes below n) and pk (the kth prime)

This uses a basic Sieve of Eratosthenes to enumerate the primes up to some fixed bound (in a relatively memory efficient manner), and then allows this cached information to be used for things like enumerating the primes, and factorisation via trial division.

(Despite the name, it can sieve the primes up to 109 in about 5 seconds.)

Source

# Example

Let's find the 10001st prime. The basic idea is to enumerate the primes and then take the 10001st in that list.

Unfortunately, `Primes::sieve` takes an upper bound, and it gives us no information beyond this; so we really need some way to find an upper bound to be guaranteed to include the 10001st prime. If we had an a priori number we could just use that, but we don't (for the purposes of this example, anyway). Hence, we can either try filtering with exponentially larger upper bounds until we find one that works (e.g. doubling each time), or just take a shortcut and use deeper mathematics via `estimate_nth_prime`.

```// find our upper bound
let (_lo, hi) = slow_primes::estimate_nth_prime(10001);

// find the primes up to this upper bound
let sieve = slow_primes::Primes::sieve(hi as usize);

// (.nth is zero indexed.)
match sieve.primes().nth(10001 - 1) {
Some(p) => println!("The 10001st prime is {}", p), // 104743
None => unreachable!(),
}```

# Using this library

Just add the following to your `Cargo.toml`:

``````[dependencies.slow_primes]
git = "https://github.com/huonw/slow_primes"
``````

## Structs

 PrimeIterator Iterator over the primes stored in a sieve. Primes Stores information about primes up to some limit. StreamingSieve A segmented sieve that yields only a small run of primes at a time.

## Functions

 as_perfect_power 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`). as_prime_power Return `Some((p, k))` if `x = p^k` for some prime `p` and `k >= 1` (that is, including when `x` is itself a prime). estimate_nth_prime Gives estimated bounds for pn, the `n`th prime number, 1-indexed (i.e. p1 = 2, p2 = 3). estimate_prime_pi Returns estimated bounds for π(n), the number of primes less than or equal to `n`. is_prime_miller_rabin Test if `n` is prime, using the deterministic version of the Miller-Rabin test.

## Type Definitions

 Factors (prime, exponent) pairs storing the prime factorisation of a number.