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 " % 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 heteroge

#!/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 " % 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.

StackExchange Code Review Q#11317, answer score: 5