4
\$\begingroup\$

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

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.

\$\endgroup\$
3
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Looking at the forum for problem 10, I'm guessing you are referring to Lucy_Hedgehog's answer? I don't understand it at all. Went straight over my head. And I don't understand what you mean by producing numbers as products, can you give an example? And finally, how could I count numbers without producing them? (Sorry, relatively new to programming) \$\endgroup\$ – Nemo Jun 28 '15 at 5:26
  • \$\begingroup\$ @Nemo New to programming... than try something simpler. Really. This is a pretty hard problem. +++ I'm sure that understanding the answer is the simplest way to solve the PU 521. +++ Producing numbers as products... it's like sieving, to solve the problem up to 10**9, create a boolean[] visited, mark all multiples of 2, then all not-yet-marked multiples of 3, then 5, etc.... and count it and you have the answer. For 10**12 that's too slow. +++ I can tell you that there are 999 multiples of 1001 below one million. No producing involved. \$\endgroup\$ – maaartinus Jun 28 '15 at 5:37
2
\$\begingroup\$

If you want to get the prime numbers, you can do that easily and fast with a sieve, for instance the Sieve of Erathostenes. You only need to find all prime numbers up to \$\sqrt{10^{12}} = 10^6\$. Then you can start counting. The number of numbers having smallest prime factor 2 is half of all the numbers. The number of 3 as a prime factor is one third, but we need to disregard half of those because they are also divisible by 2. When we get to 5, then we need two steps: First count all 5s, then disregard all 3s and 2s, but include the 6s because those will be counted twice. You may want to read up on Inclusion-Exclusion, which explains this more in detail.

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to Code Review! Your post looks good, I've fixed up the TeX formatting a bit. \$\endgroup\$ – ferada Jun 28 '15 at 11:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.