# Prime factorization of a number

I'm trying to learn Python through the excellent online book Dive Into Python 3. I have just finished chapter 2 about data types and felt like trying to write a program on my own.

The program takes an integer as input and factorizes it into prime numbers:

$python main.py 6144 6144 -> (2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3)$ python main.py 253789134856
253789134856 -> (2, 2, 2, 523, 60657059)


I'd like to know if I could improve it in any way. Or if I've used any bad practice and so on.

#!/usr/bin/python

import sys
import math

def prime_factorize(n):
factors = []
number = math.fabs(n)

while number > 1:
factor = get_next_prime_factor(number)
factors.append(factor)
number /= factor

if n < -1: # If we'd check for < 0, -1 would give us trouble
factors[0] = -factors[0]

return tuple(factors)

def get_next_prime_factor(n):
if n % 2 == 0:
return 2

# Not 'good' [also] checking non-prime numbers I guess?
# But the alternative, creating a list of prime numbers,
# wouldn't it be more demanding? Process of creating it.
for x in range(3, int(math.ceil(math.sqrt(n)) + 1), 2):
if n % x == 0:
return x

return int(n)

if __name__ == "__main__":
if len(sys.argv) != 2:
print("Usage: %s <integer>" % sys.argv[0])
exit()

try:
number = int(sys.argv[1])
except ValueError:
print("'%s' is not an integer!" % sys.argv[1])
else:
print("%d -> %s" % (number, prime_factorize(number)))


Edit:

@JeffMercado: Interesting link as I haven't encountered this before. And yes, the memoization technique should be easy to implement in my case since it is basically the same as the Fibonacci example.

In the Fibonacci example, they have a map (dictionary in Python?) outside the function, but should I do that? Global variables “are bad”? If that's the case, where does it belong? In the function prime_factorize() and I pass the map as an argument? I'm having a hard time deciding things like this, but I guess it gets easier with experience...

@WinstonEwert:

Prime factorization really only makes sense for integers. So you really use abs not fabs.

I couldn't find abs when I ran help(math), only fabs. I thought fabs was my only choice but I just found out that abs doesn't even reside in the math module. Fixed.

Tuples are for heterogeneous data. Keep this a list. It is conceptually a list of numbers, and it so it should be stored in a python list not a tuple.

You write that tuples are for heterogeneous data. I searched SO and many seems to be of this opinion. However, in the book I'm following, the author gives a few points for using a tuple:

Tuples are faster than lists. If you’re defining a constant set of values and all you’re ever going to do with it is iterate through it, use a tuple instead of a list.

It makes your code safer if you “write-protect” data that doesn’t need to be changed. Using a tuple instead of a list is like having an implied assert statement that shows this data is constant, and that special thought (and a specific function) is required to override that.

That is why a returned a tuple. Is the author's points valid or just not in this case?

Your expression, int(math.ceil(math.sqrt(n)) + 1) seems to be more complicated that it needs to be. Couldn't you get by with int(math.sqrt(n) + 1).

The upper value of range was unnecessarily complicated. Fixed.

Again, why are you trying to support something that isn't an int?

I was returning int(n) from get_next_prime_factor(n) since the number that is passed in to the function becomes a float when I divide it (in prime_factorize), so if I return just n from the function, I return a float which gets added to the list 'factors'. When I then print the factors, I get e.g. '11.0' as the last factor for the number 88.

Any other way to fix that?

I'd pass an exit code to indicate failure

Should I just exit(1) or something like that?

• You should definitely create a list of the prime numbers that you've found and keep it as your find more. The higher the numbers you get the more iterations you would have to do unnecessarily. Keyword is, Dynamic programming. Look at the Fibonacci Sequence example as it should be very similar. – Jeff Mercado Apr 29 '12 at 23:11
• @JeffMercado: aka memoization. – Joel Cornett Apr 30 '12 at 22:50
• In response to your tuple question, you should only use tuples if you are returning a fixed number of values. If it varies, then a list would be more appropriate. The amount of numbers you are returning here varies so you should be using lists. – Jeff Mercado May 1 '12 at 2:04
• If you want to respond to the reviewers, its best to comment on the posts. We aren't notified if you edit your answer. – Winston Ewert May 2 '12 at 1:04
• Regarding tuple performance: the question of tuple vs list performance is complicated. It depends on what you are doing. Its not true to simply state that tuples are faster. In this case, you waste a bunch of time converting your list into the tuple. That time is going to be far more significant than anytime you might save by using tuples. – Winston Ewert May 2 '12 at 1:26

## 3 Answers

#!/usr/bin/python

import sys
import math

def prime_factorize(n):
factors = []
number = math.fabs(n)


Prime factorization really only makes sense for integers. So you really use abs not fabs.

    while number > 1:
factor = get_next_prime_factor(number)
factors.append(factor)
number /= factor

if n < -1: # If we'd check for < 0, -1 would give us trouble
factors[0] = -factors[0]

return tuple(factors)


Tuples are for heterogeneous data. Keep this a list. It is conceptually a list of numbers, and it so it should be stored in a python list not a tuple.

def get_next_prime_factor(n):
if n % 2 == 0:
return 2

# Not 'good' [also] checking non-prime numbers I guess?
# But the alternative, creating a list of prime numbers,
# wouldn't it be more demanding? Process of creating it.
for x in range(3, int(math.ceil(math.sqrt(n)) + 1), 2):


Your expression, int(math.ceil(math.sqrt(n)) + 1) seems to be more complicated that it needs to be. Couldn't you get by with int(math.sqrt(n) + 1).

        if n % x == 0:
return x

return int(n)


Again, why are you trying to support something that isn't an int?

if __name__ == "__main__":
if len(sys.argv) != 2:
print("Usage: %s <integer>" % sys.argv[0])
exit()


I'd pass an exit code to indicate failure

    try:
number = int(sys.argv[1])
except ValueError:
print("'%s' is not an integer!" % sys.argv[1])
else:
print("%d -> %s" % (number, prime_factorize(number)))


Algorithmwise, it will be more efficient to keep a list. They key is to keep information about the primes used between calls. In particular, you want a list that indicates the smallest prime factor for example

factors[9] = 3, factors[15] = 3, factors[42] = 21


A simple modification of the Sieve of Eratosthenes should suffice to fill that in. Then easy lookups into the list should tell you exactly which prime is next.

• int(math.ceil(math.sqrt(n)) + 1) equates to int(sqrt(n)) + 2 actually. You're right though, this is unnecessary as there are no prime factors > sqrt(n) – Joel Cornett Apr 30 '12 at 5:18
• Using the Sieve might be problematic since it seems the range of numbers to support is unbounded. It will need to support up to the range of long numbers since 253789134856 is well beyond the range of int. – Jeff Mercado Apr 30 '12 at 5:58
• @JeffMercado, good point. – Winston Ewert Apr 30 '12 at 22:57

It would only make a difference in the case of products of big primes, but you could remember the latest factor found and restart from here (and not from 3):

def prime_factorize(n):
factors = []
number = abs(n)
factor = 2

while number > 1:
factor = get_next_prime_factor(number, factor)
factors.append(factor)
number /= factor

if n < -1:  # If we'd check for < 0, -1 would give us trouble
factors[0] = -factors[0]

return factors

def get_next_prime_factor(n, f):
if n % 2 == 0:
return 2

# Not 'good' [also] checking non-prime numbers I guess?
# But the alternative, creating a list of prime numbers,
# wouldn't it be more demanding? Process of creating it.
for x in range(max(f, 3), int(math.sqrt(n) + 1), 2):
if n % x == 0:
return x

return n


I also agree about the strangeness of handling non integers, the need for an exit code, that a list is better here than tuple, etc.

You could speed this part up a bit by observing for factor>3, that every factor will be either of the form 6k - 1, or 6k + 1, for integers k >= 1.

def get_next_prime_factor(n, factor):
if n % 2 == 0:
return 2
if n % 3 == 0:
return 3

for x in range(int(factor/6), int(math.sqrt(n)/6) + 1):
if n % (6*x-1) == 0:
return 6*x-1

if n % (6*x+1) == 0:
return 6*x+1

return int(n)


As suggested before, it will also greatly help you to keep track of the last found factor.