Расчет последовательных простых факторизаций

Question

Все знают, что факторизация сложна. Но что, если бы я хотел вычислить простую факторизацию каждого числа от 2 до N? Если мы вычислили первичную факторизацию каждого числа в [2, n-1] и если число n имеет малый простой множитель, то вычисление факторизации n легко, потому что примерно 73% чисел делятся на 2, 3 или 5. Конечно, некоторые случаи, например, когда n является произведением двух простых чисел одинакового размера, все еще трудны, но в среднем мы можем ожидать, что эта проблема будет достаточно простой, поскольку мы должны иметь только чтобы найти один фактор из числа, чтобы свести нашу проблему к двум задачам, которые мы решали ранее (т.е. с учетом d и n/d).

Я спрашиваю, потому что мне интересно найти сумму квадратов r(n) ( http://mathworld.wolfram.com/SumofSquaresFunction.html), так как n колеблется от 0 до N. Это число равно целому числу. точки по кругу. Как видно на странице Wolfram Mathworld, есть формула для r(n) в терминах простой факторизации n.

Пока я выбрал два подхода:

1) Подсчитайте количество точек, удовлетворяющих x^2 + y^2 = n, с 0

2) Вычислить простую факторизацию n (независимо, каждый раз) и вычислить r(n) с этой информацией.

Экспериментально, 2) кажется быстрее, но он не масштабируется по сравнению с первым методом, который медленнее, но не делает ЭТО намного медленнее. Я заинтересован в вычислении R(N) = сумма от 1 до N от r(n) для 40 цифр N.

Другой вариант - использовать что-то вроде сита Эратосфена, чтобы сгенерировать все простые числа до N, затем объединить их различными способами, чтобы вычислить простые факторизации всех чисел от 2 до N, и использовать ту же формулу, что и раньше.

У кого-нибудь есть идеи, какой из этих вариантов может работать наиболее эффективно? 1) проще всего реализовать, начинается медленно, но, вероятно, достаточно хорошо масштабируется. 2) начинается быстро, плохо масштабируется, быстрое нахождение фактора, безусловно, труднее осуществить, но оно может быть очень хорошим, если оно модифицировано для использования запоминания предыдущих факторизаций или с использованием некоторой первичной техники генерации, как упомянуто выше.

Даже если бы 1) было самым быстрым, мне все равно было бы интересно узнать самый быстрый способ генерации всех простых факторизаций от 0 до N.

Answer 1

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