"""Integer primality (deterministic Miller-Rabin for n < 2^64) and factorization
(Pollard's rho with Brent cycle detection + deterministic Miller-Rabin).
"""
import math
import random


_SMALL_PRIMES = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)


def is_prime(n: int) -> bool:
    if n < 2:
        return False
    for p in _SMALL_PRIMES:
        if n == p:
            return True
        if n % p == 0:
            return False
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for a in (2, 3, 5, 7, 11, 13, 17):
        if a % n == 0:
            continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        composite = True
        for _ in range(s - 1):
            x = x * x % n
            if x == n - 1:
                composite = False
                break
        if composite:
            return False
    return True


def _pollard_brent(n: int) -> int:
    if n % 2 == 0:
        return 2
    if n % 3 == 0:
        return 3
    while True:
        c = random.randrange(1, n)
        f = lambda x: (x * x + c) % n
        y, m, g, r, q = random.randrange(2, n), 1, 1, 1, 1
        while g == 1:
            x = y
            for _ in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for _ in range(min(m, r - k)):
                    y = f(y)
                    diff = x - y
                    if diff < 0:
                        diff = -diff
                    q = q * diff % n
                g = math.gcd(q, n)
                k += m
            r *= 2
            m *= 2
        if g == n:
            while True:
                ys = f(ys)
                diff = x - ys
                if diff < 0:
                    diff = -diff
                g = math.gcd(diff, n)
                if g != 1:
                    break
        if g != n:
            return g


def factor(n: int) -> list[int]:
    if n < 0:
        return factor(-n)
    if n < 2:
        return []
    n = abs(n)
    factors = []

    def _factor(m):
        if m == 1:
            return
        if is_prime(m):
            factors.append(m)
            return
        d = _pollard_brent(m)
        _factor(d)
        _factor(m // d)

    for p in _SMALL_PRIMES:
        while n % p == 0:
            factors.append(p)
            n //= p
    if n > 1:
        _factor(n)
    factors.sort()
    return factors


def totient(n: int) -> int:
    if n < 1:
        raise ValueError("n must be >= 1")
    if n == 1:
        return 1
    fs = factor(n)
    result = n
    for p in set(fs):
        result -= result // p
    return result


if __name__ == "__main__":
    import sys
    for arg in sys.argv[1:]:
        n = int(arg)
        print(n, is_prime(n), factor(n))