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.


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


import prime
import random

def test_coprime():
    assert prime.get_coprime(10) == 9
    assert prime.get_coprime(10) == 1

    assert prime.get_coprime(100000) == 64937

def test_fermat_primality():
    assert prime.fermat_primality(1000) == False