Finding The Greatest Prime Divisor (the Fastest Program Possible)

I was checking the problems on http://projecteuler.net/ The third problem is as follows: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the

Solution 1:

The problem with your solution is that you don't take your found prime factors into account, so you're needlessly checking factors after you've actually found the largest one. Here's my solution:

def largest_prime_factor(n):
    largest =None

    for i in range(2, n):
        while n % i == 0:
            largest = i
            n //= iif n == 1:
            return largest

    if n > 1:
        return n

Project Euler problems are more about mathematics than programming, so if your solution is too slow, it's probably not your language that's at fault.

Note that my solution works quickly for this specific number by chance, so it's definitely not a general solution. Faster solutions are complicated and overkill in this specific case.

Solution 2:

This might not be the fastest algorithm but it's quite efficient:

defprime(x):
    if x in [0, 1]:
        returnFalsefor n in xrange(2, int(x ** 0.5 + 1)):
        if x % n == 0:
            returnFalsereturnTruedefprimes():
    """Prime Number Generator

    Generator an infinite sequence of primes

    http://stackoverflow.com/questions/567222/simple-prime-generator-in-python
    """# 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 = 2whileTrue:
        if q notin 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 += 1defprimefactors(x):
    if x in [0, 1]:
        yield x
    elif prime(x):
        yield x
    else:
        for n in primes():
            if x % n == 0:
                yield n
                breakfor factor in primefactors(x // n):
            yield factor

Usage:

>>> list(primefactors(100))
[2, 2, 5, 5]

Solution 3:

My code which seems enough fast to me. Using collections.defaultdict() would make the code of primes() abit cleaner but I guess the code would loose some speed due to importing it.

defprimes():
    """Prime number generator."""
    n, skip = 2, {}
    whileTrue:
        primes = skip.get(n)
        if primes:
            for p in primes:
                skip.setdefault(n + p, set()).add(p)
            del skip[n]
        else:
            yield n
            skip[n * n] = {n}
        n += 1defun_factor(n):
    """Does an unique prime factorization on n.

    Returns an ordered tuple of (prime, prime_powers)."""if n == 1:
        return ()
    result = []
    for p in primes():
        (div, mod), power = divmod(n, p), 1while mod == 0:
            if div == 1:
                result.append((p, power))
                returntuple(result)
            n = div
            div, mod = divmod(n, p)
            if mod != 0:
                result.append((p, power))
            power += 1

Test run:

>>> un_factor(13195)
((5, 1), (7, 1), (13, 1), (29, 1))
>>> un_factor(600851475143)
((71, 1), (839, 1), (1471, 1), (6857, 1))
>>> un_factor(20)
((2, 2), (5, 1))

EDIT: Minor edits for primes() generator based on this recipe.

EDIT2: Fixed for 20.

EDIT3: Replaced greatest_prime_divisor() with un_factor().

Solution 4:

def getLargestFactor(n):
    maxFactor = sqrt(n)
    lastFactor = n
    while n%2 == 0:
        n  /= 2
        lastFactor = 2for i in xrange(3,int(maxFactor),2 ):
        ifsqrt(n) < i:
             return n
        while n%i == 0 and n > 1:
            n  /= ilastFactor= i
    return lastFactor

This should be fairly efficient. Dividing each factor all out, this way we only find the prime factors. And using the fact that there can only be one prime factor of a number larger than sqrt(n).