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 pk (the kth 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 1010 (455052511) on the author's laptop (i7-3517U).

Source

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, 108 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 (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 nth 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

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