# Pollard p-1 factorization Method

import math

from sympy import isprime


# function to generate
# prime factors
def pollard(number: int) -> int:
    # defining base.
    base: int = 2
    # defining exponent.
    exponent: int = 2

    # iterate till a prime factor is obtained
    while (True):
        # recomputing a as required
        base = (base ** exponent) % number
        # finding gcd of a-1 and n
        # using math function
        d = math.gcd((base - 1), number)

        # check if factor obtained
        if (d > 1):
            # return the factor
            return d

        # else increase exponent by one
        # for next round
        exponent += 1


if __name__ == "__main__":
    # user input
    NUMBER = int(input("Enter the number whose factor is to be found: "))
    # temporarily storing n
    num = NUMBER
    # list for storing prime factors
    ans: list[int] = []

    # iterated till all prime factors
    # are obtained
    while (True):
        # function call
        d = pollard(num)
        # add obtained factor to list
        ans.append(d)
        # reduce n
        r = int(num / d)

        if (isprime(r)):
            # both prime factors obtained
            ans.append(r)
            break

        # reduced n is not prime, so repeat
        else:
            num = r

    print("Prime factors of", NUMBER, "are", *ans)
