Prime Factorization algorithm

Question

I'm trying to write function to find the prime factorization of a given number. It need not be fast, or efficient, it just needs to work.

Here is my idea:

• Pick a number and a starting point (which will be 2).
• If the number is divisible by 2, add one to a counter and divide the number by 2.
• When the number is not divisible by 2, change your starting point to 3.
• Repeat.

Here is my code:

def ffs(num):

factors={}

n=2

while n<num:

    while num%n==0:

        num=num/n

        if n in factors:
            factors[n]+=1
        else:
            factors[n]=1


    n+=1

return factors

I run into some problems early on. When I try to evaluate ffs(6) I should get {2: 1, 3:1}, but instead I get {2: 1}. Can someone try to spot my error?

Answer 1

So, your algorithm seems fine, except you haven't properly talked about your termination condition. It should actually be when num == 1. Therefore...

def ffs(num):
    factors = {}
    n = 2

    while num != 1:
        while num % n == 0:
            num /= n
            if n in factors:
                factors[n] += 1
            else:
                factors[n] = 1
        n += 1

    return factors

print ffs(6)

We could also use collections.defaultdict, to simplify the code a bit:

from collections import defaultdict

def ffs(num):
    factors = defaultdict(lambda: 0)
    n = 2

    while num != 1:
        while num % n == 0:
            factors[n] += 1
            num /= n
        n += 1

    return dict(factors)

print ffs(6)

Both of these will output:

{2: 1, 3: 1}