Crate primes

A basic library for finding primes, providing a basic Iterator over all primes. It is not as fast as slow_primes, but it is meant to be easy to use!

The simplest usage is simply to create an Iterator:

use primes::{Sieve, PrimeSet};

let mut pset = Sieve::new();

for (ix, n) in pset.iter().enumerate().take(10) {
    println!("Prime {}: {}", ix, n);
}

This library provides methods for generating primes, testing whether a number is prime, and factorizing numbers. Most methods generate primes lazily, so only enough primes will be generated for the given test, and primes are cached for later use.

Source

Example: Find the first prime after 1 million

use primes::{Sieve, PrimeSet};

let mut pset = Sieve::new();
let (ix, n) = pset.find(1_000_000);

println!("Prime {}: {}", ix, n);

Example: Find the first ten primes after the thousandth prime

use primes::{Sieve, PrimeSet};

let mut pset = Sieve::new();
for (ix, n) in pset.iter().enumerate().skip(1_000).take(10) {
    println!("Prime {}: {}", ix, n);
}

Example: Find the first prime greater than 1000

use primes::{Sieve, PrimeSet};

let mut pset = Sieve::new();
let (ix, n) = pset.find(1_000);
println!("The first prime after 1000 is the {}th prime: {}", ix, n);

assert_eq!(pset.find(n), (ix, n));

For more info on use, see PrimeSet, a class which encapsulates most of the functionality and has multiple methods for iterating over primes.

This also provides a few functions unconnected to PrimeSet, which will be faster for the first case, but slower in the long term as they do not use any caching of primes.

Structs

PrimeSetIter

An iterator over generated primes. Created by PrimeSet::iter or PrimeSet::generator

Sieve

A prime generator, using the Sieve of Eratosthenes method. This is asymptotically more efficient than the Trial Division method, but slower earlier on.

TrialDivision

A prime generator, using the Trial Division method.

Traits

PrimeSet

PrimeSetBasics

Functions

factors

Find all prime factors of a number Does not use a PrimeSet, but simply counts upwards

factors_uniq

Find all unique prime factors of a number

is_prime

Test whether a number is prime. Checks every odd number up to sqrt(n).