#3 Largest prime factor

The prime factors of 13195 are 5, 7, 13, and 29. What is the largest prime factor of the number 600851475143?

---

Prime number generator.

# Sieve of Eratosthenes
# Code by David Eppstein, UC Irvine, 28 Feb 2002
# http://code.activestate.com/recipes/117119/

def gen_primes():
    """ Generate an infinite sequence of prime numbers.
    """
    # Maps composites to primes witnessing their compositeness.
    # This is memory efficient, as the sieve is not "run forward"
    # indefinitely, but only as long as required by the current
    # number being tested.
    #
    D = {}
    
    # The running integer that's checked for primeness
    q = 2
    
    while True:
        if q not in D:
            # q is a new prime.
            # Yield it and mark its first multiple that isn't
            # already marked in previous iterations
            # 
            yield q
            D[q * q] = [q]
        else:
            # q is composite. D[q] is the list of primes that
            # divide it. Since we've reached q, we no longer
            # need it in the map, but we'll mark the next 
            # multiples of its witnesses to prepare for larger
            # numbers
            # 
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]
        
        q += 1

 

For every prime number from the generator, this function will check if the given number n is evenly divisible by it.

def primefactor(n):
    prime_factors = []
    for prime in gen_primes():
        if n % prime == 0:
            n /= prime
            prime_factors.append(prime)
        else:
            break
    return prime_factors

 

Since the generator is infinite this function will be an infinite loop. I have to set an escape condition.

def primefactor(n):
    prime_factors = []
    for prime in gen_primes():
        if prime > n:
            break
        else:
            if n % prime == 0:
                n /= prime
                prime_factors.append(prime)
            else:
                break
    return prime_factors

 

It would be more convenient if this function does a "prime factorization". I will change the prime_factors to a dictionary. The keys are prime factors and the values are the powers. Let's add a repeating process and count how many times it can be divided into a prime.

def primefactor(n):
    prime_factors = dict({})
    for prime in gen_primes():
        if prime > n:
            break
        else:
            count = 0
            while True:
                if n % prime == 0:
                    n /= prime
                    count += 1
                else:
                    if count != 0:
                        prime_factors[prime] = count
                    break
    return prime_factors

>>> primefactor(600851475143)
{71: 1, 839: 1, 1471: 1, 6857: 1}

The answer is 6857.