Всем известно, что факторизация сложна. Но что, если бы я хотел рассчитать простую факторизацию каждого числа от 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) Подсчитать число точек, удовлетворяющее х^2 + у^2 = п, с 0 < < х у, а затем использовать некоторые перестановки аргумент, чтобы найти r (n)
2) Вычислить простую факторизацию n (независимо, каждый раз) и вычислить r (n) с помощью этой информации.
Экспериментально, 2) кажется более быстрым, но он не масштабируется хорошо, по сравнению с первым методом, который работает медленнее, но не получает ЭТО намного медленнее. Я интересуюсь вычислением R (N) = суммы от 1 до N от r (n) для 40 цифр N.
Другим вариантом было бы использовать что-то вроде сита Эратосфена для генерации всех простых чисел до N, затем объединить их различными способами, рассчитать простые факторизации всех чисел от 2 до N и использовать ту же формулу, что и раньше.
Есть ли у кого-нибудь идеи, какие из этих вариантов могут работать наиболее эффективно? 1) проще всего реализовать, начинает медленно, но, вероятно, достаточно хорошо масштабируется. 2) быстро запускается, не масштабируется хорошо, быстрый поиск факторов, безусловно, сложнее реализовать, но может очень хорошо, если он модифицирован для использования memoization предыдущих факторизаций или использования какой-либо простой технологии генерации, как упомянуто выше.
Даже если 1) является самым быстрым, я бы до сих пор заинтересован в изучении быстрого способа генерации всех простых факторизации от 0 до N.
Вы можете использовать модифицированное сито для определения диапазона чисел. Я не знаю, будет ли это быстрее, но это определенно довольно просто. Но сохранение всех простых коэффициентов чисел 10^40 не кажется хорошей идеей. – biziclop
Почему downvote? – MadMonty