# Project Euler: Problem 3
#
# The prime factors of 13195 are 5, 7, 13 and 29.
#
# What is the largest prime factor of the number 600851475143 ?
#
##################
# Solution: 6857
# Best time:  0.3705568313598633
##################

from time import time

def get_primes(limit):
    '''
        Implementation of Sieve algorithm
        Limit <= 10**8
    '''
    a = [True] * limit
    a[0] = a[1] = False
    for i, isprime in enumerate(a):
        if isprime:
            yield i
            for n in range(i*i, limit, i):
                a[n] = False

def get_factors(number):
    return set(factor for k in range(1, int(number**0.5)+1) for factor in (k, number//k) if number%k == 0)

def get_max_prime_factor(factors, limit):
    factors_max = max(k for k in factors if k != limit)
    list_primes = list(get_primes(int(factors_max**0.5)+1))
    return max(k for k in num_factors if k in list_primes and k != factors_max)

start = time()
number = 600851475143
num_factors = get_factors(number)

max_prime_factor = get_max_prime_factor(num_factors, number)
elapsed = time() - start
print("Result: {0}\telapsed: {1}".format(max_prime_factor, elapsed))