fork download
def prime_factors(n):
    sqrt_n = int(n**0.5)
    result = []
    if n == 1: return result
    while n%2 == 0:  # check for divisor = 2
        result.append(2)
        n /= 2 
    while n%3 == 0:  # check for divisor = 3
        result.append(3)
        n /= 3
    div = 5  # start with divisor = 6k-1 with k = 1
    while div <= sqrt_n:
        if n == 1: break
        changed = n%div == 0
        while n%div == 0:  # check for i = 6k-1
            result.append(div)
            n /= div
        div += 2  # proceed to 6k+1 = 6k-1 + 2
        if not changed: changed = n%div == 0
        while n%div == 0:  # check for i = 6k+1
            result.append(div)
            n /= div
        div += 4  # proceed to 6(k+1)-1 = 6k+5 = 6k+1 + 4
        if changed: sqrt_n = int(n**0.5)
    if n != 1: result.append(n)
    return result

def largest_prime_factor(n):
    if n == 1: return None
    m = int(n**0.5)
    while n%2 == 0: n /= 2
    if n == 1: return 2
    while n%3 == 0: n /= 3
    if n == 1: return 3
    i = 5
    while i <= m:
        changed = n%i == 0
        while n%i == 0: n /= i
        if n == 1: return i
        i += 2
        if not changed: changed = n%i == 0
        while n%i == 0: n /= i
        if n == 1: return i
        i += 4
        if changed: m = int(n**0.5)
    if n != 1: return n
    
    
if __name__ == '__main__':
    print prime_factors(600851475143)
    print largest_prime_factor(600851475143)
Success #stdin #stdout 0.01s 7728KB
stdin
Standard input is empty
stdout
[71, 839, 1471, 6857L]
6857