import random

# Test fermata - snrawdzanie czy liczba jest nierwsza

def potegowanieimod(b, k, n):
    y = 1
    while k > 0:
        if k & 1:
            y = y*b % n
        b = b**2 % n
        k = k >> 1
    return y


def fermat(k, n):
    i = 0
    while i < k:
        a = random.randint(1, n - 1)
        if potegowanieimod(a, (n - 1), n) == 1:
            i = i + 1
        else:
            return False
    return True

n = int(input("Podaj liczbę do sprawdzenia: "))
print("Liczba jest pierwsza: {}".format(fermat(100, n)))