Finding the prime factors of a number in Python 2

Question

I’ve created a function that takes a number and, if it’s prime, tells you so, or if it’s composite, gives you the prime factors of the number (and if it’s 1, tells you that it’s neither).

Theoretically it should work for an infinitely large number, but at 8 digits it starts to slow down significantly, particularly if the prime factors are large. I’m fairly new at Python, so I’d welcome any feedback, especially on how to make it faster.

I’m aware that there are things I could have done more efficiently from the start — some of which I’ve become aware from looking at other Python questions in this same vein on this site — but while I would find advice like ‘this bit’s ill-conceived, rip it out and write something else entirely’ helpful, I’d prefer best-practices things, and ways to make it faster without totally changing the premises (as it were).

I haven’t annotated it because (as far as I’m aware), it’s fairly basic; any old hack could write this, but obviously I can annotate if you’d like.

Thanks!

Here’s the code (in Python 2):

import math
def prime_factors(y):
 n = y
 def is_prime(x):
    count = 0
    if x > 1:
      for i in range(2, x):
        if x % i != 0: 
          count += 1
        else:
          return False
          break
    else:
        return True
    if count != 0:
        return True 
    if x == 2:
      return True
 def make_p_lst(x):
   z = []
   for i in range(2, x):
     if is_prime(i) == True:
       z.append(i)
   return z
 
 c = 0
 c = int(math.sqrt(y) + 1)
 prime_lst = []
 prime_lst = make_p_lst(c)
 p = is_prime(y)
 if p == True and y != 1:
   print '%s is prime.' % (y)
   return 'Thus, its\' only factors are 1 and itself.'
 elif y != 1:
   print '%s is composite, here are its\' prime factors: ' % (y)
   factors_lst = []
   while is_prime(y) != True:
      for i in prime_lst:
        if y % i == 0:
          y = y/i
          factors_lst.append(i)
   factors_lst.append(y)
   factors_lst.sort()
   if factors_lst[0] == 1: 
     factors_lst.remove(1)
   n = factors_lst
   return n
 else:
   return '1 is neither prime nor composite.'
print prime_factors(871)

Answer 1

• (Obligatory) Python 2 is end of life it is advised to upgrade to Python 3.
• You should always indent with 4 spaces in Python. This makes it easier for me to read what is inside prime_factors and what is outside of it.
• It's common to surround top level functions (prime_factors) with 2 empty lines, and other functions (is_prime, make_p_lst) with one empty line.

Otherwise your whitespace is good. Here is what it'd look like with these fixed.

import math


def prime_factors(y):
    def is_prime(x):
        count = 0
        if x > 1:
            for i in range(2, x):
                if x % i != 0: 
                    count += 1
                else:
                    return False
                    break
        else:
            return True
        if count != 0:
            return True 
        if x == 2:
            return True

    def make_p_lst(x):
        z = []
        for i in range(2, x):
            if is_prime(i) == True:
                z.append(i)
        return z
        
    n = y
    c = 0
    c = int(math.sqrt(y) + 1)
    prime_lst = []
    prime_lst = make_p_lst(c)
    p = is_prime(y)
    if p == True and y != 1:
        print '%s is prime.' % (y)
        return 'Thus, its\' only factors are 1 and itself.'
    elif y != 1:
        print '%s is composite, here are its\' prime factors: ' % (y)
        factors_lst = []
        while is_prime(y) != True:
            for i in prime_lst:
                if y % i == 0:
                    y = y / i
                    factors_lst.append(i)
        factors_lst.append(y)
        factors_lst.sort()
        if factors_lst[0] == 1: 
            factors_lst.remove(1)
        n = factors_lst
        return n
    else:
        return '1 is neither prime nor composite.'


print prime_factors(871)

• You don't need is_prime or make_p_lst to be inside prime_factors. This is making your code harder to read as it's not immediately apparent that you are not using them as closures.

• All code after a return will not run. This means the break in is_prime will not run.

• Your is_prime function doesn't handle 0 and 1 correctly.

  >>> [(i, is_prime(i)) for i in range(6)]
  [(0, True), (1, True), (2, True), (3, True), (4, False), (5, True)]
  

  Since it's not already we can change your code to be simpler by removing all the count parts. Then we can just special case 0 and 1.

  def is_prime(x):
      if x <= 1:
          return False
  
      for i in range(2, x):
          if x % i == 0: 
              return False
      return True
  

• In make_p_lst you shouldn't do if is_prime(i) == True instead you should just use if is_prime(i).

• In prime_factors you shouldn't do while is_prime(y) != True instead you should just use while not is_prime(y).

• We can simplify the code by using a list comprehension. This is just syntactic sugar for building the list as your are now.

• You don't need to initialize a value and then assign it.

  c = 0
  c = int(math.sqrt(y) + 1)
  prime_lst = []
  prime_lst = make_p_lst(c)
  

  You can just remove the first of each.

  c = int(math.sqrt(y) + 1)
  prime_lst = make_p_lst(c)
  

• By fixing is_prime we don't need the and y != 1 check.

• Getting the prime factors should be put into a function.

• Many of your variable names are hard to understand or follow. You should really use better names than x, i, c, y, etc.

  Additionally I prefer using plurals to denote a list of items. For example the following is much easier to read.

  for prime in primes:
      # do something with prime
  

• Because I changed is_prime to make 1 no longer return True, the code to get the prime factors no longer works for 1. However we can fix that by moving the while loop into the for loop. Then we can merge it with the if.

  This has the benefit that we don't have to loop through prime_lst multiple times and we won't call is_prime.

def is_prime(number):
    if number <= 1:
        return False
    for divisor in range(2, number):
        if number % divisor == 0: 
            return False
    return True


def primes_below(limit):
    return [number for number in range(2, limit) if is_prime(number)]


def get_prime_factors(number):
    if number == 0:
        return []
    primes = primes_below(int(number ** 0.5 + 1))
    factors = []
    for prime in primes:
        while number % prime == 0:
            number /= prime
            factors.append(prime)
    if number != 1:
        factors.append(number)
    return factors


def prime_factors(number):
    prime = is_prime(number)
    if prime:
        print '%s is prime.' % (number)
        return 'Thus, its\' only factors are 1 and itself.'
    elif number != 1:
        print '%s is composite, here are its\' prime factors: ' % (number)
        return get_prime_factors(number)
    else:
        return '1 is neither prime nor composite.'


print prime_factors(871)

At this point it'd be good to rethink how your code works. prime_factors sometimes returns the prime factors. However other times it returns a string. It also prints to the screen which is not helpful if I only want the prime factors.

Your function prime_factors should do no string manipulation.

This means it should return a list of prime factors and only a list of prime factors.

• 0 would return an empty list.
• 1 would return an empty list.
• 2 would return 2.
• 4 would return 2 and 2.

And so we can see get_prime_factors is what should actually be prime_factors.

And so we can change main to use only get_prime_factors and only print. Returning from main is not a good idea.

def is_prime(number):
    if number <= 1:
        return False
    for divisor in range(2, number):
        if number % divisor == 0: 
            return False
    return True


def primes_below(limit):
    return [number for number in range(2, limit) if is_prime(number)]


def prime_factors(number):
    if number == 0:
        return []
    primes = primes_below(int(number ** 0.5 + 1))
    factors = []
    for prime in primes:
        while number % prime == 0:
            number /= prime
            factors.append(prime)
    if number != 1:
        factors.append(number)
    return factors


def main(number):
    factors = prime_factors(number)
    if not factors:
        print '1 is neither prime nor composite.'
    elif len(factors) == 1:
        print '%s is prime.' % (number)
        print 'Thus, its only factors are 1 and itself.'
    else:
        print '%s is composite, here are its prime factors: ' % (number)
        print factors


if __name__ == '__main__':
    main(871)

Answer 2

Why Python 2? As Peilonrayz said, Python 2 died 7 months ago and should really be replaced with Python 3 for all new projects. Personally, just f- strings are more than enough of a reason (even if you want to ignore other new features and security concerns).

Finding prime factors can be done in a far more efficient manner. The basic idea is: keep dividing your number by the smallest number greater than 1, as long as you can. Because it is the smallest divisor, it must be a prime (if it wasn't, its factors would divide your number too, so it wouldn't be the smallest divisor). This completely removes the need for is_prime.

As for Python, I'd go with generators, because they easily convert to a list if needed, but they also help you avoid lists when you don't need them (for example, in loops). Even better, they cut down computation in some cases (for example: find the smallest prime).

Also, every file, class, method, and function should have a doctring, with one line summary, any further explanations (if needed), and a list of arguments, raised exceptions, and return values, thoroughly explained.

As a matter of convenience and showing two very similar cases, I also added a unique flag, which lets you get all prime factors or only one of each (see the docstring below for the explanation).

"""
A module for finding prime factors of a number.
"""

from __future__ import print_function


def prime_factors(x, unique=False):
    """
    Return a generator of prime factors of `x`.

    :param x: An `int` for which the prime factors are generated.
    :param unique: A Boolean flag. If `True`, only unique prime factors are
        return (i.e., 2 and 3 for `x = 24`). If `False`, all of them are
        returned (i.e., 2, 2, 2, and 3 for `x = 24`).
    :return: A generator of prime factors of `x`.
    """
    x = abs(x)
    p = 2
    while x > 1:
        is_first = True
        while x % p == 0:
            if is_first or not unique:
                yield p
                is_first = False
            x //= p
        p += 1


if __name__ == "__main__":
    for x in (0, 1, 2, 3, 4, 5, 24, -24, 871):
        print("Number:", x)
        print("  All prime factors of %d: " % x, list(prime_factors(x)))
        print(
            "  Unique prime factors of %d:" % x,
            list(prime_factors(x, True)),
        )

        # This can be done with `if abs(x) > 1`, but for educational purposes
        # we go with more general, catch-the-exception approach:
        try:
            print(
                "  The smallest prime factor of %d:" % x,
                next(prime_factors(x)),
            )
        except StopIteration:
            print("  Number %d has no prime factors." % x)

Let me also add a Python 3 version, with the only difference being the use of f-strings. Note how much more readable (and pleasant to write) this is:

"""
A module for finding prime factors of a number.
"""


def prime_factors(x, unique=False):
    """
    Return a generator of prime factors of `x`.

    :param x: An `int` for which the prime factors are generated.
    :param unique: A Boolean flag. If `True`, only unique prime factors are
        return (i.e., 2 and 3 for `x = 24`). If `False`, all of them are
        returned (i.e., 2, 2, 2, and 3 for `x = 24`).
    :return: A generator of prime factors of `x`.
    """
    x = abs(x)
    p = 2
    while x > 1:
        is_first = True
        while x % p == 0:
            if is_first or not unique:
                yield p
                is_first = False
            x //= p
        p += 1


if __name__ == "__main__":
    for x in (0, 1, 2, 3, 4, 5, 24, -24, 871):
        print(f"Number: {x}")
        print(f"  All prime factors of {x}: {list(prime_factors(x))}")
        print(f"  Unique prime factors of {x}: {list(prime_factors(x, True))}")

        # This can be done with `if abs(x) > 1`, but for educational purposes
        # we go with more general, catch-the-exception approach:
        try:
            print(
                f"  The smallest prime factor of {x}:",
                next(prime_factors(x)),
            )
        except StopIteration:
            print(f"  Number {x} has no prime factors.")

Answer 3

ways to make it faster without totally changing the premises (as it were).

I'm not sure where you draw that line, but I'll try to stay on the right side of it by suggesting a series of incremental changes to the "meat" of the algorithm,

   while is_prime(y) != True:
      for i in prime_lst:
        if y % i == 0:
          y = y/i
          factors_lst.append(i)

Handling repeated factors

Currently a repeated factor requires the inner for-loop to complete, and y to be tested for primality again (which by the way effectively finds a factor as well, since it uses Trial Division, but it does not return that factor), then the inner for-loop has to start from scratch first trying a bunch of small divisors that have already been rejected in the previous iteration of the outer loop.

That duplication/re-scanning could be avoided by removing all instances of a given factor at once, by changing the if to while:

for i in prime_lst:
    while y % i == 0:
        y = y / i
        factors_lst.append(i)

As a bonus, the list of factors is created in order, so it does not need to be sorted .. except that factors_lst.append(y) can append either a big prime or 1. Rather than appending y blindly, sorting the list, and then removing 1 from the front, I would suggest conditionally appending y:

if y > 1:
    factors_lst.append(y)

Removing prime_lst

Building prime_lst is actually the slowest part of the code. It costs more time than it saves by the effect of only trying primes as factors. Simply trying a range of integers is already faster. But what range? Actually a range from 2 to c is too much: it does not take into account that y is going down as factors are found. So there is no pre-determined range that fits the bill, but it could be done like this:

i = 2
while i * i <= y:
    while y % i == 0:
        y = y / i          # note: use // in Python 3
        factors_lst.append(i)
    i = i + 1

Where i * i <= y is a similar sort of condition as i < c, except it takes the changing y into account, without repeatedly taking square roots.

Note that checking whether i is a prime is not necessary. y % i == 0 can only succeed if i is prime, because if i was a composite a * b, then a and b would have already been divided out of y, making i not a divisor of y.

Doing half the work

The only even prime is 2. All other even numbers can be skipped as divisors: composites cannot be factors anyway. Unlike finding a list of primes first, just skipping even numbers is essentially free. The catch is that handling 2 itself is now trickier:

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

Time test

Factoring a fairly big composite with big factors, namely 222222227 * 232222223 * 322222223, took nearly 23 seconds on my PC. The original method struggles very hard with that, due to trying to build a very big list of primes first. Using a simple/hacky version of Pollard's rho algorithm to find factors took only 0.13 seconds.