import gmpy2
from gmpy2 import mpz, random_state, mpz_random, powmod

def is_prime_fermat(n, k=5):
    n = mpz(n)

    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False

    rand_state = random_state()

    for _ in range(k):
        a = mpz_random(rand_state, n - 3) + 2 
        result = powmod(a, n - 1, n)
        if result != 1:
            return False
    return True

n_input = input("Podaj liczbę n do przetestowania: ")
try:
    n = mpz(n_input)
except ValueError:
    print("Błędne dane: n musi być liczbą całkowitą.")
    exit()

if is_prime_fermat(n):
    print(f"{n} jest prawdopodobnie liczbą pierwszą.")
else:
    print(f"{n} jest liczbą złożoną.")