Module primes 

Prime utilities, factorization, and channel (base) selection.

All functions here are pure and have no dependency on the rest of the crate.

The “natural base” concept

The natural base of a computation is the LCM of the radicals of all denominators involved. This is the minimal base in which every fraction in the computation terminates exactly. For example, natural_base(&[6, 10, 15]) == 30, because radical(6)=6, radical(10)=10, radical(15)=15 and lcm(6,10,15)=30.

Functions

distinct_primes

The distinct prime factors of n, ascending.

extended_gcd

Extended Euclidean algorithm.

factorize

Factorize n into (prime, exponent) pairs in ascending prime order. factorize(0) and factorize(1) return an empty vector.

first_n_primes

The first n primes.

gcd

Euclidean greatest common divisor.

lcm

Least common multiple. lcm(0, x) == 0.

mod_inverse

Modular inverse of a modulo m, or None when gcd(a, m) != 1.

natural_base

Minimal exact base for a set of denominators: the LCM of their radicals.

primes_up_to

Sieve of Eratosthenes: all primes <= n.

radical

Product of the distinct prime factors of n (the squarefree kernel). radical(12) == 6, radical(1) == 1, radical(0) == 0.

termination_period

Determine how 1/n behaves when written in the given base.