Всем известно, что факторизация - это сложно. Но что, если бы я хотел вычислить разложение на простые множители каждого числа от 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 ‹x‹ y, а затем используйте некоторый аргумент перестановки, чтобы найти r (n)
2) Вычислите факторизацию n на простые множители (каждый раз независимо) и вычислите r (n) с этой информацией.
Экспериментально 2) кажется быстрее, но он плохо масштабируется по сравнению с первым методом, который медленнее, но не НАСТОЛЬКО медленнее. Меня интересует вычисление R (N) = сумма от 1 до N из r (n) для 40 цифр N.
Другой вариант - использовать что-то вроде Решета Эратосфена, чтобы сгенерировать все простые числа до N, затем объединить их различными способами, чтобы вычислить разложение на простые множители всех чисел от 2 до N, и использовать ту же формулу, что и раньше.
Есть ли у кого-нибудь идеи, какие из этих вариантов могут работать наиболее эффективно? 1) проще всего реализовать, запускается медленно, но, вероятно, неплохо масштабируется. 2) начинается быстро, плохо масштабируется, быстрый поиск факторов, безусловно, труднее реализовать, но может очень хорошо работать, если его модифицировать для использования мемоизации предыдущих факторизаций или использования некоторой техники генерации простых чисел, как упоминалось выше.
Даже если 1) является самым быстрым, мне все равно было бы интересно узнать самый быстрый способ создания всех простых разложений от 0 до N.
