def g(x,n): #finite rng polynomial function
    return (x**2 + 1)%n

def gcd(m,n): #Euclidean algorithm
    if m < n:
        n,m = m,n
    if n == 0:
        return m
    return gcd(n,m%n)

def iter(n): #birthday paradox suggests high probability of coinciding factors
    x = 0 #initial conditions
    y = 0
    loop = 0
    while True:
        x = g(x,n) #tortoise
        y = g(g(y,n),n) #hare
        if x == y:
            loop = loop + 1
            if loop > 1: #on second loop around the 'rho', consider prime
                return int(n)
        if x-y < 0: #handle negative residues
            temp = gcd(n-x+y,n)
        else:
            temp = gcd(x-y,n) 
        if temp > 1 and temp != n:
           return int(temp)


def pollard(n): #factoring algorithm inspired by euclidean algorithm and Floyd's cycle finding algorithm
    arr = [] #stores factors
    while n != 1:
        fact = iter(n) #find factor by looping around the 'rho'
        arr.append(fact) #add factor to list 
        n = int(n/fact) #consider sub-problem
    return arr

print(pollard(9999))