List of all prime factors of a number, including repeats

This code will return a list of the prime factors of n, and the prime factors are repeated so that the product of the list is equal to n.

import math

def product(iterable):
    """ 
    Returns product of all elements in iterable 
    """
    p = 1
    for x in iterable:
        p *= x
    return p

def generate_primes(n):
    """ 
    Returns list of all primes less than or equal to n 
    """
    l = []
    for i in range(1,n+1):
        prime = True # Assume i is prime
        for j in l:
            if j > math.sqrt(n):
                break
            if i % j == 0 and j != 1:
                prime = False # Number i has been shown to be composite
                break
        if prime:
            l.append(i)
    return l

def prime_factor_set(n):
    """ 
    Returns set of the prime factors of n
    """
    return {i for i in generate_primes(n) if n % i == 0 and i != 1}

def prime_factor_list(n):
    """ 
    Returns full list of the prime factors of n, such that the product of this 
    list is equal to n 
    """
    l = list(prime_factor_set(n))
    while product(l) != n:
        r = int(n/product(l)) # Remaining number to be factored into primes
        prime_factors = prime_factor_set(r)
        l.extend(prime_factors)
    return sorted(l)

Example:

prime_factor_list(2000)

[2, 2, 2, 2, 5, 5, 5]

Some general comments:

-
Hooray for docstrings! It’s great that you’re writing these – it makes your code much easier to read and review, because I know what it’s supposed to do (and so can judge whether it does it correctly). And in general, these are pretty good docstrings.

Do note that PEP 257 says that one-line docstrings should end in a period.

-
Don’t be stingy with variable names – characters are cheap, and if you write more descriptive names, the code becomes much easier to follow.

For example, in generate_primes(), known_primes is better than l.

-
There are a few minor PEP 8 violations – in particular, space after comma in function arguments (for i in range(1,n+1)) and a double-space before inline comments.

-
Use generators! Generators allow you to do lazy evaluation of large iterables (such as a list of prime numbers) – which can make a big difference for performance. If you’re not familiar with generators, they’re a really powerful tool in Python. I recommend Ned Batchelder’s PyCon talk.

Okay, now comments on the specific functions:

-
product() – no comments, looks fine.

-
generate_primes() – it’s a bit hard to follow, because of the short variable names. It might be helpful to have some logic explaining the motivation behind the different steps, although on inspection it appears to be mostly sound.

It does return 1 as a prime number. Convention usually dictates that 1 isn’t a prime number – there might be a good reason to deviate from convention, but you should document it if so.

You could also hard-code 2 as the only even prime number, and then just check odd numbers after that – skip half the checks you have to do.

This is what a revised version of that function might look like, with better comments and variables names, and using generators:

def generate_primes(n):
    """Generates all the primes less than or equal to n."""
    if n == 1:
        return

    known_primes = [2]
    yield 2

    for i in range(3, n+1, 2):

        # Assume that i is prime until proven otherwise.
        is_prime = True

        for existing_prime in known_primes:

            # As i  math.sqrt(n):
                break

            # If i is a multiple of another prime number, then i itself
            # cannot be prime.
            if i % existing_prime == 0:
                is_prime = False
                break

        if is_prime:
            known_primes.append(i)
            yield i

-
prime_factor_set() – aside from the quirk with i != 1 to account for generate_primes(), this is fine. But let’s make it a lazy generator:

def prime_factors(n):
    """Generates the prime factors of n."""
    for prime in generate_primes(n):
        if n % prime == 0:
            yield prime

-
prime_factor_list() – I find the docstring and name a little confusing. It sounds like you’re returning a list of prime factors – in fact, what you have is the prime factorisation of n.

Your approach makes many calls into prime_factor_set, which in turn calls generate_primes. This is quite an expensive function, so you minimise the number of calls you require. In fact, you can get away with just 1. Get a list of all the prime factors of n, and then use them to chip away at n until they’re exhausted. Like so:

def prime_factorization(n):
    """Generates the prime factorization of n."""
    for factor in prime_factors(n):
        while n % factor == 0:
            yield factor
            n /= factor
        if n == 1:
            break

With our new generators-based approach, this is significantly faster than the original, because it only computes the prime factors of n as it requires them.

StackExchange Code Review Q#144325, answer score: 7