import math


def get_poly_coeffs(a, n):
    n += 1
    coeffs = []
    for j in range(n):
        coeffs.append(math.factorial(n - 1) // (math.factorial(j) * math.factorial(n - 1 - j)))
    for i in range(len(coeffs)):
        coeffs[i] = coeffs[i] * (a ** i)
    return coeffs


def euler_func(value, power=1):
    if power == 1:
        return value - 1
    else:
        return value ** power - value ** (power - 1)


def get_order(n, r):
    pwr = n
    cnt = 1
    while pwr % r != 1:
        pwr *= n
        cnt += 1
    return cnt


def check_power(a, n):
    powered_a = a
    b = 1
    while powered_a <= n:
        if powered_a == n:
            return True, b
        powered_a *= a
        b += 1
    return False, 0


def check_prime(e):
    for i in range(2, int(math.sqrt(e))):
        if e % i == 0:
            return False
    return True


def get_all_divisors_brute(n):
    for i in range(1, int(n / 2) + 1):
        if n % i == 0:
            yield i
    yield n


def get_only_prime_divisors(inp):
    g = 1
    prime_divisors = []
    while g != inp:
        for i in get_all_divisors_brute(inp):
            if check_prime(i) and inp % i == 0 and i != 1:
                inp = inp / i
                prime_divisors.append(int(i))
                break
    return prime_divisors


def get_euler(r):
    p_d = get_only_prime_divisors(r)
    euler_func_mult = []
    for el_1 in p_d:
        el_pw = 0
        for el_2 in p_d:
            if el_1 == el_2:
                el_pw += 1
        euler_func_mult.append((el_1, el_pw))

    tmp = []
    for euler_mult in set(euler_func_mult):
        tmp.append(euler_func(*euler_mult))
    euler_func_mult = tmp

    phi_value = 1
    for elem in euler_func_mult:
        phi_value *= elem
    return phi_value


def check_polinom(a, n):
    coeffs = get_poly_coeffs(a, n)
    coeffs.remove(coeffs[0])
    coeffs[-1] -= a
    if not(coeffs[-1]):
        coeffs.remove(coeffs[-1])
    for cf in coeffs:
        if cf % n:
            return False
    return True


def find_smallest_order(n):
    r = 1
    while True:
        r += 1
        if math.gcd(r, n) != 1:
            continue
        o_r = get_order(n, r)
        if o_r > (math.log2(n)) ** 2:
            return r


def aks_test(n):
    r = find_smallest_order(n)
    phi_r = get_euler(r)
    border = math.floor(math.sqrt(phi_r) * math.log2(n))

    for a in range(2, border):
        is_powered, b = check_power(a, n)

        if is_powered and b > 1:
            return False

        if 1 < math.gcd(a, n) < n and a <= r:
            return False

        if n <= r:
            return True

        if not check_polinom(a, n):
            return False

    return True


if __name__ == "__main__":
    print("Введите число n:")
    n = int(input())
    result = aks_test(n)
    if result:
        print(f"Число {n} является простым")
    else:
        print(f"Число не является простым")