4
\$\begingroup\$

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]
\$\endgroup\$

1 Answer 1

6
\$\begingroup\$

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 <= n, if i is coprime to all the primes <= sqrt(n),
                # it must be that i itself is prime.
                if existing_prime > 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.

\$\endgroup\$
1
  • \$\begingroup\$ In prime_factorization, you need to write n //= factor to avoid a (possibly lossy) conversion to floating point. I would expect list(prime_factorization(2**1025)) == [2] * 1025 to evaluate to True, but the code here raises OverflowError: integer division result too large for a float. \$\endgroup\$ Oct 17, 2016 at 9:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.