Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Below is the code for knowing all the prime factors of a number. I think there must be some better way of doing the same thing. Also, please tell me if there are some flaws in my code.

def factorize(num):
    res2 = "%s: "%num
    res = []
    while num != 1:
        for each in range(2, num + 1):
            quo, rem = divmod(num, each)
            if not rem:
                res.append(each)
                break
        num = quo
    pfs = set(res)
    for each in pfs:
        power = res.count(each)
        if power == 1:
            res2 += str(each) + " "
        else:
            res2 += str(each) + '^' + str(power) + " "
    return res2
share|improve this question
    
Which version of Python are you using? Optimizations may change with the version. –  Morwenn Feb 2 '13 at 14:11
add comment

1 Answer

def factorize(num):
    res2 = "%s: "%num

You'd be much better off to put the string stuff in a seperate function. Just have this function return the list of factors, i.e. res and have a second function take res as a parameter and return the string. That'd make your logic simpler for each function.

    res = []

Don't needlessly abbreviate. It doesn't save you any serious amount of typing time and makes it harder to follow your code.

    while num != 1:
        for each in range(2, num + 1):

To be faster here, you'll want recompute the prime factors of the numbers. You can use the Sieve of Eratosthenes. Just keep track of the prime factors found, and you'll just be able to look them up.

            quo, rem = divmod(num, each)
            if not rem:
                res.append(each)
                break
        num = quo

Your function dies here if you pass it a zero.

    pfs = set(res)

Rather than a set, use collections.Counter, it'll let you get the counts at the same time rather then recounting res.

    for each in pfs:
        power = res.count(each)
        if power == 1:
            res2 += str(each) + " "
        else:
            res2 += str(each) + '^' + str(power) + " "

String addition is inefficient. I'd suggest using "{}^{}".format(each, power). Also, store each piece in a list and then use " ".join to make them into a big string at the end.

    return res2
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.