Finding the prime factors of a number in Python 2

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)

• Welcome to code review! I hope you get some good answers. – pacmaninbw Jul 31 at 12:21
• @pacmaninbw Thanks, I hope so too :D – Fivesideddice Jul 31 at 12:22
• Why Python 2, not 3? – superb rain Jul 31 at 13:59

• (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)

• while is_prime(y) != True should be while not is_prime(y) or - if you really want comparison with True, then while is_prime(y) is not True. – Vedran Šego Jul 31 at 13:13
• @VedranŠego Doh, yeah I completely skipped over that thanks! I'll update that when I push out the next update. – Peilonrayz Jul 31 at 13:14
• Two quick points: (1) Basic prime checking can be written as a one-liner: number > 1 and all(number % divisor for divisor in range(2, number)); (2) For this problem, it is actually unneccessary to do prime checking at all since the smallest factor of a number is guaranteed to be a prime. – GZ0 Aug 1 at 3:56
• @GZ0 All I care about is improving readability and maintainability. Others have commented on performance. Additionally just because you can put something on one line doesn't mean you should. – Peilonrayz Aug 1 at 9:14
• Thanks for all the help! – Fivesideddice Aug 3 at 8:31

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.")

• After 2 and 3 all primes are of the form 6*i +/- 1. Thus you can reduce the number of iterations in your main loop, at the cost of making the code a little more complicated and ugly. The bigger savings (for larger numbers) would come from identifying when p becomes greater the square root of x and stopping at that point. However, either of these changes might be considered "changing the algorithm" by OPs rules. – President James K. Polk Aug 1 at 13:28
• @PresidentJamesK.Polk, you can, but then we can ask: where to stop with such improvements? I am happy with a simple algorithm that improves complexity. Anyone wanting to improve this (drop the number of iterations without affecting the complexity), either with treating 2 as a special case or with doing what you suggested or doing something even more advanced, can easily replace p += 1 with their choice of pivot. Don't get me wrong: I think that your remark is a valid and valuable contribution, but I also feel that it is better suited for a completely separate question. – Vedran Šego Aug 1 at 13:54
• @VedranŠego Seeing as the OP wrote "I’d welcome any feedback, especially on how to make it faster" and voices concern about efficiency, and seeing that the original code was very inefficient and could be made more efficient to easily, I'd say PresidentJamesK.Polk's comment was on topic for this question. – Rosie F Aug 1 at 14:20
• Another way to improve the main loop is to exit if x*x > p, in which case p is prime. This will avoid wasting time seeking factors x<p of a number p, if p happens to be prime. – Rosie F Aug 1 at 14:22
• You mean p * p > x, right? Yes, that would help in the case when the biggest prime factor has multiplicity 1. However, this would need to be done after each p += 1 (or its variant; ref. the comment by President James K. Polk), which means an extra multiplication in each step. Without a thorough analysis, I'm unsure if this would be good or bad in the general case. I feel that it would be more useful to compute sqrt(x) when x changes, and than just compare p against that. – Vedran Šego Aug 1 at 20:37

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.

• In fact, do only one-third of the work: Test 2 and 3 separately, then every subsequent prime is 6k-1 or 6k+1 as k ranges through positive integers. (This still includes some composites, but skips more of them than just testing odds.) A smart way to do this is to unroll the loop once and increment by 2 between the copies and by 4 between the bottom and top of the new loop. – Eric Towers Jul 31 at 23:55
• @EricTowers or 8/30 or 48/210 etc using the same principle – harold Aug 1 at 8:47
• +1 for mentioning Pollard's rho. – Rosie F Aug 1 at 14:23
• Nice, you can also use $6n + 1, 6n - 1$, however I found my Sieve of Eratosthenes to be the fastest in pure Python so far. – Peilonrayz Aug 2 at 5:39