Перебор чисел ‹n, определение разложения каждого числа на простые множители

Я хочу перебрать каждое число ‹N и знать разложение на простые множители каждого числа. У меня вопрос, как лучше всего это сделать?

Я знаю, что могу использовать метод пробного деления, чтобы найти разложение на простые множители данного числа, и просто повторить это для каждого числа меньше N, но это неэффективно и занимает больше времени, чем создание каждого числа из известных простых множителей. . Я написал ниже реализацию генерации каждого числа, меньшего N, из всех простых множителей, меньших N. Есть ли более быстрый способ сделать это? Я пытаюсь использовать тот факт, что, поскольку я делаю это для всех чисел меньше N, чтобы сэкономить время вычислений, вместо этого применяю метод пробного деления.

Цель, которую я пытаюсь достичь: у меня есть алгоритм, который я хочу запускать для каждого числа, меньшего N. Для этого алгоритма мне нужна факторизация на простые множители каждого числа. Я пытаюсь получить факторизацию каждого числа на простые множители за минимальное время. На самом деле мне не нужно хранить простые факторизации, мне просто нужно запустить мой алгоритм с простой факторизацией. (Алгоритм решения (curNum, curFactors) в коде)

Я написал программу на python3, которая рекурсивно генерирует каждое число со знанием его простых множителей, но это довольно медленно. (Время обработки составляет ~ 58 секунд при N = 10 ^ 7. Функция решения ничего не делает для этого теста.)

curFactors - это список, в котором каждый четный элемент является индексом простого числа в факторизации, а каждый нечетный элемент является показателем простого числа. Я выровнял его из списка списков, чтобы сэкономить время вычислений. Простой начальный индекс используется для того, чтобы я не пересчитывал числа дважды. В настоящее время Solve ничего не делает, поэтому я могу протестировать эту функцию.

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[i]
        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")

Кто-нибудь знает, как это сделать лучше?