Fast Number Factorization in Python

Here's my implementation to factorize a positive integer:

def is_prime(n):
    if n == 1:
        return False
    if n % 2 == 0:
        return False
    i = 3
    while i * i <= n:
        if n % i == 0:
            return False
        i += 2
    return True

# @timeit
def prime_factors(n):
    prime_factor_list = []
    while not n % 2:
        prime_factor_list.append(2)
        n //= 2
    while not n % 3:
        prime_factor_list.append(3)
        n //= 3
    i = 5
    while n != 1:
        if is_prime(i):
            while not n % i:
                prime_factor_list.append(i)
                n //= i
        i += 2

    return prime_factor_list

How can I improve this code in speed and make it pythonic?

prime_factors()

The single greatest improvement to performance that you could make would be to remove the call to is_prime() altogether. If all factors smaller than i have been removed from n already, then i could not possibly be composite.

The next improvement you could make would be to turn prime_factors() into a generator. The function would no longer need to resize and recopy prime_factor_list whenever the list needs to grow beyond its estimated size. Furthermore, the caller could start making use of initial results before the entire factorization is finished.

Using three lines (i = 5, while n != 1, and i += 2) to structure the loop — something that would be succinctly written in C as a for (i = 5; n != 1; i += 2) header — is un-Pythonic. Such counting loops are usually better written using some kind of range(), xrange(), enumerate(), or something from itertools. Here, itertools.chain() and itertools.count() would be appropriate.

Without changing the spirit of your algorithm, I would write:

import itertools

def prime_factors(n):
    for i in itertools.chain([2], itertools.count(3, 2)):
        if n <= 1:
            break
        while n % i == 0:
            n //= i
            yield i

is_prime()

As mentioned above, you don't need is_prime() at all, if your only goal is to implement prime_factors().

However, if you wanted to implement is_prime() anyway, you could tighten it up a bit. My main recommendation would be to avoid performing the i * i multiplication with each iteration. You would probably be better off computing the \$\sqrt{n}\$ limit just once.

Then, as with the other function, you should express the loop more Pythonically using range() or xrange(). Actually, you wouldn't need an explicit loop; you could use any() instead.

So, if we stick to your algorithm in spirit, we could tighten up the implementation like this:

def is_prime(n):
    if n < 3 or n % 2 == 0:
        return n == 2
    else:
        return not any(n % i == 0 for i in range(3, int(n**0.5 + 2), 2))

StackExchange Code Review Q#121862, answer score: 11