Calculating sum of smallest prime factors for 2 < n < 10**12

I am trying to calculate the sum of the smallest prime factors of n, where 2 < n < 1012, and get the remainder of this sum when divided by 109:

require 'prime'
puts "Started at #{Time.now}."
num = 10**12
sum = 0
(2..num).each { |n| sum += n.prime_division[0][0] }
sum = sum % 10**9
p sum
puts "Finished at #{Time.now}."

Understanding that the smallest prime factor of any even number is 2, and the smallest prime factor of any prime number is itself, I made the following function:

def findSmallestPrimeFactor(number)
  return 2 if number.even?
  return number if Prime.prime? number
  return number.prime_division[0][0]
end

However I feel this would have no effect on the program's run time as #prime_division works well enough on any number.

Is there any way to shorten the runtime of this program? I have been told that efficient implementation will allow the program to finish in under 1 minute, however I can't see how I can do this without iterating over every number between 2 and one trillion (10**12), which will take several days regardless.

Sorry, too long for a comment (this isn't a real review, but it isn't a CR what you need).

This is Project Euler 521 and providing a full answer here would spoil the fun. If you really want to cheat, google it out.


Is there any way to shorten the runtime of this program?

There are many ways and you'll need more than one:

• Iterating till 10**12 alone is too slow, even if you did just a simple sum (one hour maybe).

• Determining if a number is a prime, even with a good sieve takes quite some time as well.

Without much thinking, I agree with you that the runtime will be many days.

Your question is actually not about code optimization, but about finding a smarter algorithm. Smarter by a few orders of magnitude. A wonderful hint can be found in forum for problem 10, page 5.

It's solvable without this wonderful idea, too, but it took my computer half an hour. Instead of factoring numbers, I produced them as products, which is much faster when you really want all of them. The next idea is that you don't really need to produce them, counting is enough.

StackExchange Code Review Q#94963, answer score: 3