Prime factorization of a number

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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.