

In [1]:

    
def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        while n % i == 0:
            factors.append(i)
            n //= i
        i += 1
    if n > 1:
        factors.append(n)
    return factors



In [2]:

    
prime_factors(2*2)









    Out[2]:





[2, 2]



In [3]:

    
n = 600851475143
%timeit prime_factors(n)
prime_factors(n)









    



1000 loops, best of 3: 546 µs per loop






    Out[3]:





[71, 839, 1471, 6857L]



In [4]:

    
def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        while n % i == 0:
            factors.append(i)
            n //= i
        if i > 2:
            i += 2
        else:
            i = 3
    if n > 1:
        factors.append(n)
    return factors



In [5]:

    
n = 600851475143
%timeit prime_factors(n)
prime_factors(n)









    



1000 loops, best of 3: 290 µs per loop






    Out[5]:





[71, 839, 1471, 6857L]



In [6]:

    
from math import sqrt



In [7]:

    
def prime_factors(n):
    i = 2
    factors = []
    sqrt_n = int(sqrt(n))
    while i <= sqrt_n:
        while n % i == 0:
            factors.append(i)
            n //= i
        sqrt_n = int(sqrt(n))
        if i > 2:
            i += 2
        else:
            i = 3
    if n > 1:
        factors.append(n)
    return factors



In [8]:

    
n = 600851475143
%timeit prime_factors(n)
prime_factors(n)









    



1000 loops, best of 3: 534 µs per loop






    Out[8]:





[71, 839, 1471, 6857L]

That was much much slower, so the square root stuff is out.



In [9]:

    
def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        while True:
            quotient, remainder = divmod(n, i)
            if remainder != 0:
                break
            factors.append(i)
            n = quotient
        if i > 2:
            i += 2
        else:
            i = 3
    if n > 1:
        factors.append(n)
    return factors



In [10]:

    
n = 600851475143
%timeit prime_factors(n)
prime_factors(n)









    



1000 loops, best of 3: 515 µs per loop






    Out[10]:





[71, 839, 1471, 6857L]



In [11]:

    
def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        while True:
            quotient, remainder = divmod(n, i)
            if remainder != 0:
                break
            factors.append(i)
            n = quotient
        if i > 2:
            i += 2
        else:
            i = 3
    if n > 1:
        factors.append(n)
    return factors



In [12]:

    
n = 600851475143
%timeit prime_factors(n)
prime_factors(n)









    



1000 loops, best of 3: 463 µs per loop






    Out[12]:





[71, 839, 1471, 6857L]



In [13]:

    
def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        while n % i == 0:
            factors.append(i)
            n //= i
        i += (2 if i > 2 else 1)
    if n > 1:
        factors.append(n)
    return factors



In [14]:

    
n = 600851475143
%timeit prime_factors(n)
prime_factors(n)









    



1000 loops, best of 3: 307 µs per loop






    Out[14]:





[71, 839, 1471, 6857L]



In [15]:

    
def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        while n % i == 0:
            factors.append(i)
            n //= i
        i += (i > 2) + 1
    if n > 1:
        factors.append(n)
    return factors



In [16]:

    
n = 600851475143
%timeit prime_factors(n)
prime_factors(n)









    



1000 loops, best of 3: 341 µs per loop






    Out[16]:





[71, 839, 1471, 6857L]



In [17]:

    
def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        while n % i == 0:
            factors.append(i)
            n //= i
        i += (i > 2)
        i += 1
    if n > 1:
        factors.append(n)
    return factors



In [18]:

    
n = 600851475143
%timeit prime_factors(n)
prime_factors(n)









    



1000 loops, best of 3: 377 µs per loop






    Out[18]:





[71, 839, 1471, 6857L]

For divisors above two, it was surprising how much faster dividing only by odd numbers was, in spite of how many statements that took. It seems that division is very slow. So the fewer numbers one divides by, the faster it is. Dividing only by primes would be an obvious thing to try.

Multiplication also seems to be slow. Replacing "while i * i <= n:" of cell #4 with "while i <= sqrt_n:" in cell #7 was much slower.