from math import gcd, sqrt, log, exp


def get_only_prime_divisors(n):
    factors = []
    if (n % 2 == 0):
        factors.append(2)

    while (n % 2 == 0):
        n = n // 2

    for i in range(3, int(sqrt(n)) + 1, 2):
        if (n % i == 0):
            factors.append(i)

        while (n % i == 0):
            n = n // i

    if (n > 2):
        factors.append(n)

    return factors


def erathosphene(n):
    is_prime = [True] * n
    p = 2
    while p * p < n:
        cur = p * p;
        while cur < n:
            is_prime[cur] = False;
            cur += p;
        while not is_prime[p + 1]:
            p += 1;
        p += 1
    primes = []
    for i, p in enumerate(is_prime):
        if p:
            primes.append(i)
    return primes[2:]


def get_factor_base(n):
    m = sqrt(exp(sqrt(log(n) * log(log(n)))))
    factor_base = erathosphene(int(m))
    return factor_base


def dixon_factorization(n):
    factor_base = get_factor_base(n)
    print("Фактор база: ", factor_base)
    smooth_b = []
    for b in range(int(sqrt(n)), n):
        a = b ** 2 % n
        for fact in factor_base:
            f = fact ** 2 % n
            if a == f:
                smooth_b.append((b, fact))

    factors = []
    for a, fact in smooth_b:
        factor = gcd(a - fact, n)
        if factor != 1:
            factors.append(factor)

    return list(set(factors))


def main():
    print("Введите нечётное целое число n:")
    n = int(input())
    factors = dixon_factorization(n)
    print(f"Простые множители {n}:", factors)


if __name__ == "__main__":
    main()