There are a number of ways to check if a number is a prime number. Some of these are Probabilistic tests. Like the Fermat primality test.
Using Coprime integers
I wrote this when I working on an example for testing random-based code.
examples/python/fermat_primality_test/prime.py
import random
import math
def get_coprime(n):
while True:
coprime = random.randrange(n)
if math.gcd(coprime, n) == 1:
return coprime
def fermat_primality(n, count = 1):
for _ in range(count):
a = get_coprime(n)
if (a ** (n-1)) % n != 1:
return False
return True
examples/python/fermat_primality_test/test_prime.py
import prime
import random
def test_coprime():
random.seed(1)
assert prime.get_coprime(10) == 9
assert prime.get_coprime(10) == 1
assert prime.get_coprime(100000) == 64937
def test_fermat_primality():
random.seed(1)
assert prime.fermat_primality(1000) == False