To install the package use pip:
pip install primefinders
Some algorithm on prime numbers. You can find all the functions in the file primefinders/
In this release the Algorithm uses :
- Fermat's test (based on Fermat's theorem)
Future Algorithms will use :
- Eratosthenes sieve based
- Prime generating functions
- Miller-Rabin primality test
- Euler's phi(n) i.e., the number of integers less than n which have no common factor with n
- Lucas-Lehmer and LCG
- Atiyah's \Gamma
- Language: Python 3.6 (also works on 3.5 and 3.7)
- Package:
- Basic python packages were preferred
- Matplotlib v2.0 - graph and math
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"
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
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.
With (n)
from primefinders import primefinders
primefinders.about()
primefinders.calculate(1697)
# With n the number you want to test
fermat(n)
primefinders.fermat(1697)If n is prime then ∀ a ∈[1, ..., n-1]
a^(n-1) ≡ 1 (mod n) ⇔ a^(n-1) = kn + 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 primefinders import toolkit
>>>
from primefinders import lucas_lehmer
# With as a parameter the upper limit
lucas_lehmer(10)
>>> 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 primefinders import sieve_eratosthenes
# With as a parameter the upper limit
sieve_eratosthenes(10)
>> {2: [4, 6, 8], 3: [6, 9], 5: [], 7: []}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.
