To install the package use pip:
pip install nprime
uv is a fast Python package manager. To install nprime with uv:
uv add nprime
Interested in contributing? See our Contributing Guide for development setup instructions, testing guidelines, and contribution workflows.
Some algorithm on prime numbers. You can find all the functions in the file nprime/pryprime.py
Algorithm developed :
- Eratosthenes sieve based
- Fermat's test (based on Fermat's theorem)
- Prime generating functions
- Miller Rabin predictive algorithm
- Prime factorization
- Perfect number check
- AKS deterministic primality test
- Language: Python 3.10+ (supports Python 3.10, 3.11, 3.12, 3.13, 3.14)
- Package:
- Basic python packages were preferred
- Matplotlib >=3.9.0 - graph and math
For the tests coverage, there's codecov which is run during the GitHub Actions CI pipeline.
Here are a bit of information to help understand some of the algorithms
"≡" means congruent, a ≡ b (mod m) implies that
m / (a-b), ∃ k ∈ Z that verifies a = kn + b
which implies:
a ≡ 0 (mod n) <-> a = kn <-> "a" is divisible by "n"
A strong pseudoprime to a base a is an odd composite number n
with n-1 = d·2^s (for d odd) for which either a^d = 1(mod n) or a^(d·2^r) = -1(mod n) for some r = 0, 1, ..., s-1
Implementation of the sieve of erathostenes that discover the primes and their composite up to a limit. It returns a dictionary:
- the key are the primes up to n
- the value is the list of composites of these primes up to n
from nprime import sieve_eratosthenes
# With as a parameter the upper limit
sieve_eratosthenes(10)
>> {2: [4, 6, 8, 10], 3: [9], 5: [], 7: []}The previous behaviour can be called using the trial_division which uses the Trial Division algorithm
This sieve mark as composite the multiple of each primes. It is an efficient way to find primes.
For n ∈ N with n > 2 and for ∀ a ∈[2, ..., √n] then n/a ∉ N is true.
A Probabilistic algorithm taking t randoms numbers a and testing the Fermat's theorem on number n > 1
Prime probability is right is 1 - 1/(2^t)
Returns a boolean: True if n passes the tests.
from nprime import fermat
# With n the number you want to test
fermat(n)If n is prime then ∀ a ∈[1, ..., n-1]
a^(n-1) ≡ 1 (mod n) ⇔ a^(n-1) = kn + 1
A probabilistic algorithm which determines whether a given number (n > 1) is prime or not.
The miller_rabin tests is repeated t times to get more accurate results.
Returns a boolean: True if n passes the tests.
from nprime import miller_rabin
# With n the number you want to test
miller_rabin(n)For n ∈ N and n > 2,
Take a random a ∈ {1,...,n−1}
Find d and s such as with n - 1 = 2^s * d (with d odd)
if (a^d)^2^r ≡ 1 mod n for all r in 0 to s-1
Then n is prime.
The test output is false of 1/4 of the "a values" possible in n,
so the test is repeated t times.
Return the prime factorization of a positive integer n as a sorted list.
Each prime factor appears as many times as it divides n.
from nprime import prime_factors
prime_factors(12)
>> [2, 2, 3]
prime_factors(100)
>> [2, 2, 5, 5]The fundamental theorem of arithmetic states that every integer n > 1 can be represented uniquely as a product of prime powers:
n = p1^a1 * p2^a2 * ... * pk^ak
Where p1 < p2 < ... < pk are primes and a1, a2, ..., ak are positive integers.
For example 360 = 2^3 × 3^2 × 5, so prime_factors(360) returns [2, 2, 2, 3, 3, 5].
The algorithm uses trial division: divide n by each candidate divisor d starting from 2 up to √n.
If n is still greater than 1 after exhausting all candidates, then n itself is prime.
Check if a positive integer n is a perfect number.
Returns a boolean: True if n is perfect.
from nprime import is_perfect
is_perfect(6)
>> True
is_perfect(28)
>> True
is_perfect(12)
>> FalseA perfect number is a positive integer that is equal to the sum of its proper positive divisors (excluding itself):
σ(n) - n = n ⇔ σ(n) = 2n
Where σ(n) is the sum of divisors function.
The first four perfect numbers are 6, 28, 496, and 8128:
6 = 1 + 2 + 3
28 = 1 + 2 + 4 + 7 + 14
Euler proved that all even perfect numbers have the form 2^(p-1) * (2^p - 1) where 2^p - 1 is a Mersenne prime.
Whether any odd perfect numbers exist remains an open problem in mathematics.
A deterministic algorithm which determines whether a given number (n > 1) is prime or not.
Unlike Fermat and Miller-Rabin it is not probabilistic, but it is much slower, so it is mostly
of theoretical interest. Returns a boolean: True if n is prime.
from nprime import aks
# With n the number you want to test
aks(n)The AKS test relies on the polynomial generalisation of Fermat's little theorem: for gcd(a, n) = 1,
n is prime if and only if
(X + a)^n ≡ X^n + a (mod n)
Checking this directly is too expensive, so AKS works in the ring (ℤ/nℤ)[X] / (X^r - 1) for a small
r, which keeps the test polynomial in the number of digits of n.