Skip to main content

Python library for primes algorithms

Project description

Generic badge PyPI version Build Status codecov Codacy Badge


To install the package use pip:

pip install nprime


Some algorithm on prime numbers.

Algorithm developed :

  • Eratosthenes sieve based
  • Fermat’s test (based on Fermat’s theorem)
  • Prime generating functions
  • Miller Rabin predictive algorithm


  • Language: Python 3.5.2
  • Package:
    • Basic python packages were preferred
    • Matplotlib v2.0 - graph and math

Integration and pipeline

Code quality is monitored through codacity. For the tests coverage, there’s codecov which is run during the Travis 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"

Strong Pseudoprime

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

Erathostene’s Sieve

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.

Erathostene example

Fermat’s Theorem

If n is prime then ∀ a ∈[1, ..., n-1]

a^(n-1) ≡ 1 (mod n) ⇔ a^(n-1) = kn + 1

Miller rabin

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.

Project details

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Filename, size & hash SHA256 hash help File type Python version Upload date
nprime-0.1.8.tar.gz (23.2 kB) Copy SHA256 hash SHA256 Source None

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN SignalFx SignalFx Supporter DigiCert DigiCert EV certificate StatusPage StatusPage Status page