factor.py

#problem 3
#Fastest approach is to use yafu rather than attempting to wrtie something yourself
#Yafu uses several modern algorithms including quadratic sieve and even the infamous general number field sieve
#but quadratic sieve is the most appropriate for the number we need to factor, and it's very fast.
#Also yafu is written in c/c++ so it's far faster than the sieve of atkins or the sieve of eranthoses

import time, os

def yafu_factor(yafu_path, yafu_bin, num):#create a function to factor a given number using yafu
    os.chdir(yafu_path)#set the working directory to where yafu binary is located
    os.system(yafu_bin + " factor(%d) > tmp" % num)#use yafu_bin factor(num) to get the factors and send them to a file tmp
    with open("tmp", "r") as yafu_res:#read the contents of the file
        res = yafu_res.read()

    factors = [ln for ln in res.split("\n") if "P" in ln]#get the prime factors and discard everything else

    for i in range(len(factors)):#clean the resulting list and convert the factors into integers (you get them as strings)
        factors[i] = int(factors[i].split("=")[1])

    return factors

def solve_EU_3():
    return max(yafu_factor("D:\One\Factoring\Yafu", "yafu-Win32.exe", 600851475143))

start = time.clock()
print("Solution is: %d. Took %d seconds." % (solve_EU_3(), time.clock() - start))
#It is so fast the time module can't measure it!