import sys
import gmpy2

# single-line comments

"""
multi-line comments
"""

def pollard_rho(n: int) -> int | None:
    n = gmpy2.mpz(n)
    x, y, d = gmpy2.mpz(2), gmpy2.mpz(2), gmpy2.mpz(1)

    while d == 1:
        x = (x*x + 1) % n
        y = (y*y + 1) % n
        y = (y*y + 1) % n
        d = gmpy2.gcd(abs(x-y), n)

    if d != n:
        return int(d)
    else:
        return None

if __name__ == '__main__':
    n = int(sys.argv[1])
    p = pollard_rho(n)
    if p:
        print('{} = {} * {}'.format(n, p, n//p))
    else:
        print('{} is prime'.format(n))