Slow prime-related algorithms
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
examples
src
.gitignore
.travis.yml
Cargo.toml
LICENSE-APACHE
LICENSE-MIT
README.md

README.md

Deprecated in favour of primal.

slow_primes

Build Status Coverage Status

Extremely 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.)

Documentation