[Python] Iterating through numbers < n, determining each number's prime factorization

I want to iterate through every number < N, and know each numbers prime factorization. My question is what is the best way to do this?

I am aware that I can I can use the trial division method to find the prime factorization of a given number, and just repeat that for every number less than N, but that is inefficient and takes longer than generating each number from the known prime factors. I have written an implementation below of generating every number that is less than N, from all of the prime factors that are less than N. Is there a faster way to do this? I am trying to use the fact that since I am doing this for all numbers less than N to save computation time, from instead doing the trial division method.

The goal that I am trying to accomplish: I have an algorithm which I want to run on every number that is less than N. For this algorithm, I need the prime factorization of each number. I am trying to get the prime factorization of each number in the minimum time. I don't actually need to store the prime factorizations, I just need to run my algorithm with the prime factorization. ( The algorithm is solve(curNum, curFactors) in the code)

I wrote a python3 program to recursively generate each number with knowledge of its prime factors, but its quite slow. (It takes ~58 seconds of processing time when N = 10^7. The function solve is doing nothing for this benchmark. )

curFactors is a list where every even element is the index of the prime in the factorization, and each odd element is that primes exponent. I flattened it from a list of lists to save computation time. The prime start index is used to ensure that I don't double count numbers. Currently Solve does nothing, just so I can benchmark this function.

def iterateThroughNumbersKnowingFactors(curNumber, curFactors, primeStartIndex):
#Generate next set of numbers
#Handle multiplying by a prime already in the factorization seperately.
for i in range(primeStartIndex+1,lenPrimes):
newNum = curNumber * primelist
if(newNum > upperbound):
break
newFactors = curFactors[:]
newFactors.append(i)
newFactors.append(1)
#Do something with this number and its factors
solve(newNum, newFactors)
#Go get more numbers
iterateThroughNumbersKnowingFactors(newNum,newFactors,i)
if(primeStartIndex > -1):
newNum = curNumber * primelist[primeStartIndex]
if(newNum > upperbound):
return
currentNumPrimes = len(curFactors)
curFactors[currentNumPrimes-1] += 1
#Do something with this number and its factors
solve(newNum, curFactors)
#Go get more numbers
iterateThroughNumbersKnowingFactors(newNum,curFactors,primeStartIndex)

upperbound = 10**7

#https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n
primelist = primesfrom2to(upperbound+1)
lenPrimes = len(primelist)

t0 = time.clock()
iterateThroughNumbersKnowingFactors(1,[],-1)
print(str(time.clock() - t0) +" seconds process time")


Does anyone know of a better way to do this?

Continue reading...