Python - Integer Factorization into Primes [closed]

Question

I wrote an integer factorization function, but after messing around with it, I realized it had problems with a few numbers...

>>> pFactors(99) # it does work for numbers with multiple of one prime factor
[3, 3, 11]
>>> pFactors(999) # however, sometimes, it doesn't
[3, 37] # the actual prime factorization of 999 is [3, 3, 3, 37]. 
>>> pFactors(88)
[2, 11]
>>> pFactors(888)
[2, 3, 37]

What's wrong in my code?

def pFactors(n):
   """Finds the prime factors of 'n'"""
   from primes import isPrime
   from math import sqrt
   pFact, limit, check, num = [], int(round(sqrt(n), 2)) + 1, 2, n
   if isPrime(n):
      return [n]
   for check in range(2, limit):
      if isPrime(check) and num % check == 0:
         pFact.append(check)
         num /= check
         if isPrime(num):
            pFact.append(num)
            break
   pFact = sorted(pFact)
   return pFact

Herodotus

You need to recalculate limit and restart the loop every time you break down the number. I would recommend a recursive approach here instead of your iterative one. – Pinkeye

Here's a naive recursive approach in five lines. – Pinkeye

Answer 1

Modify like so :

def pFactors(n): 
        """Finds the prime factors of 'n'""" 
        from math import sqrt 
        pFact, limit, check, num = [], int(sqrt(n)) + 1, 2, n 
        if n == 1: return [1] 
        for check in range(2, limit): 
             while num % check == 0: 
                pFact.append(check) 
                num /= check 
        if num > 1: 
          pFact.append(num) 
        return pFact 

for i in range(1,1000):
        print pFactors(i)

Although I liked your code as originally written, a few points :

1. You do not need isPrime. The reason is that any prime in the range up to limit, that divides num, will also be the smallest divisor of any composite that divides num, so as you divide out those primes, you will prevent the composites they make up from being found as divisors later in the range, leaving you only with the prime factors.

2. You do not need to sort the array, it is already sorted by virtue of check ascending in order.

3. The while loop added ensures that repeat factors are correctly found as long as they continue to divide num.

4. You can use congruences to filter out 2/3 of all numbers less than limit to check as divisors, can you see how?

The last few lines of the result above are :

[11, 89]
[2, 2, 5, 7, 7]
[3, 3, 109]
[2, 491]
[983]
[2, 2, 2, 3, 41]
[5, 197]
[2, 17, 29]
[3, 7, 47]
[2, 2, 13, 19]
[23, 43]
[2, 3, 3, 5, 11]
[991]
[2, 2, 2, 2, 2, 31]
[3, 331]
[2, 7, 71]
[5, 199]
[2, 2, 3, 83]
[997]
[2, 499]
[3, 3, 3, 37]

E

Ah, the while loop fixed it. Thanks for that and the other suggestions :) – Herodotus

You can get a nice representation as factors and exponents by counting repeated factors; for example [[(x, p.count(x)) for x in set(p)] for p in [pFactors(1536000)]][0] produces [(2, 12), (3, 1), (5, 3)], which means "2 to the twelfth times three to the power 1 times 5 cubed." – Justino

Answer 2

in the 999 example after you divide it by 3 the result (333) is also dividable by 3 which gives you 111 which you can also divide by 3 (and get 37). But in your code you only divide it once - what you need to do is once you find a prime that divide you current number is to keep dividing by that number until it's no longer possible.

Tera