Everyone knows that factorization is hard. But what if I wanted to calculate the prime factorization of every number from 2 to N? If we have computed the prime factorization of every number in [2, n-1] and if a number, n, has a small prime factor, then computing the factorization of n is easy, because roughly 73% of numbers are divisible by either 2, 3 or 5. Of course, some cases, such as when n is product of two prime of a similar size, are still difficult, but on average, we might expect this problem to be reasonably easy, as we should only ever have to find one factor of a number, to reduce our problem to two problems we've solved before (i.e. factoring d and n/d).
I ask because I'm interested in finding the sum of the sum of squares r(n) (http://mathworld.wolfram.com/SumofSquaresFunction.html), as n ranges from 0 to N. This counts the number of integer points in a circle. As can be seen on the Wolfram Mathworld page, there is a formula for r(n) in terms of the prime factorization of n.
I've taken two approaches thus far:
1) Count the number of points satisfying x^2 + y^2 = n, with 0 < x < y, and then use some permutation argument to find r(n)
2) Compute the prime factorization of n (independently, each time), and compute r(n) with this information.
Experimentally, 2) seems to be faster, but it doesn't scale up well, in comparison to the first method, which is slower, but doesn't get THAT much slower. I'm interested in computing R(N) = sum from 1 to N of r(n) for 40 digit N.
Another option would be to use something like the Sieve of Eratosthenes to generate all primes up to N, then combine them in various ways, to calculate the prime factorizations of all the numbers from 2 to N, and use the same formula as before.
Does anyone have any ideas which of these options may work most effectively? 1) is the easiest to implement, starts off slow, but probably scales up quite well. 2) starts off quick, doesn't scale up well, a quick factor-finding is certainly more difficult to implement, but may do very well if modified to use memoization of previous factorizations, or using some prime generating technique as mentioned above.
Even if 1) is the quickest, I'd still be interested in learning the quickest way of generating all prime factorisations from 0 to N.
The Sieve of Eratosthenes can be modified to compute the factorizations of all numbers from 2 to N. Instead of just marking off multiples of primes, keep track of each multiple as it strikes a number from the list. I give a complete solution with code at my blog.