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

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]

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.