Stuff

# Project Euler #3

from math import sqrt

def primes(n):
    """ Use sieve of Eratosthenes to find all primes <= n """
    R = {x for x in range(2,n+1)} # search space
    k = 2 # first prime
    while True:
        if k in R:
            i = 2 # first multiplier
            while k*i <= n:
                R.discard(k*i)
                i += 1;
        k += 1;
        if k >= sqrt(n): return R

def problem3(n):
    """ Find largest prime factor of n """
    R = set() # resultset
    for p in primes(int(sqrt(n))+1):
        if n % p == 0: R.add(p)
    if not len(R): return set()
    return max(R)

print problem3(600851475143)