# Arup Guha
# 10/25/2019
# Example illustrating the Fermat Factoring method.

def fermatfactor(n):

    # Smallest value of x is right above the square root of n.
    x = (int)((n**.5)+.99)

    # Keep on going.
    while True:

        # Calculate what y squared would be.
        ysqr = x*x - n

        # This is a guess for y.
        y = ysqr**.5
        tryy = int(y-1)

        # I am hoping I just have to try 3 values.
        # It might be safer to break out when (tryy+i) squared is bigger
        # than ysqr.
        for i in range(3):
            if (tryy+i)*(tryy+i) == ysqr:
                return x+(tryy+i)

        # Try the next value of x.
        x += 1


    return -1


def main():

    # The three tests we ran in class.
    N = 2923
    N = 10000000019*11000000021
    N = 10000000019*10070000321
    factor = fermatfactor(N)
    other = N//factor
    print(N,"=",factor,"x",other)

# Run it.
main()