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 :
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.
You do not need to sort the array, it is already sorted by virtue of
check
ascending in order.The while loop added ensures that repeat factors are correctly found as long as they continue to divide num.
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]