3
\$\begingroup\$

I have a Ruby program which should solve the following problem:

Consider the divisors of 30: 1,2,3,5,6,10,15,30. It can be seen that for every divisor d of 30, d+30/d is prime.

Find the sum of all positive integers n not exceeding 100 000 000 such that for every divisor d of n, d+n/d is prime.

require 'prime'

class Integer
    def factors # returns an array of all factors of self
        return (1..self).collect { |n| n if ((self/n) * n) == self }.compact
    end
end

puts "Started at #{Time.now}."
counter = 0

1.upto(100000000) do |n|
    factors = n.factors
    counter += n if factors.all? { |d| ( (d+n) / d ).is_a? Prime }
end

p counter
puts "Ended at #{Time.now}."

Problem is, while the code runs, it takes so long (not finished after several hours) that I can't actually test if I get the right answer. Is there any way to make the code more efficient so that it completes in a shorter amount of time? The problem is question #357 of Project Euler. All Euler problems should take less than one minute to solve if an efficient algorithm is being used.

\$\endgroup\$
  • \$\begingroup\$ Precompute primes. \$\endgroup\$ – Veedrac Jun 24 '15 at 21:31
  • 2
    \$\begingroup\$ Think about how even numbers will behave. Think about how odd numbers will behave. @Veedrac's suggestion is good as well. \$\endgroup\$ – rossum Jun 24 '15 at 21:47
  • 1
    \$\begingroup\$ Have you tested if for smaller values, at least? It seems to always return 0. \$\endgroup\$ – Veedrac Jun 25 '15 at 4:53
3
\$\begingroup\$
n.is_a? Prime

Doesn't work. I don't know enough Ruby to tell you why, but it doesn't. Use Prime.prime? instead.

Further, (d + n) / d is not the right calculation. You want d + n/d.

You can simplify

return (1..self).collect { |n| n if ((self/n) * n) == self }.compact

to

(1..self).select { |n| self / n * n == self }

which is even simpler as

(1..self).select { |n| (self % n).zero? }

One can do even better by making this lazy:

(1..self).lazy.select { |n| (self % n).zero? }

Then one can precompute the primes for later:

primes = Array.new(max+1) { |i| false }
Prime.each do |n|
    break if n > max
    primes[n] = true
end

1.upto(max) do |n|
    factors = n.factors
    counter += n if factors.all? { |d| primes[d + n/d] }
end

One can also note that only numbers one below primes actually need to be checked, since 1 is a factor of every number. This simplifies things:

primes = Array.new(max+1) { |i| false }
Prime.each do |prime|
    break if prime > max
    primes[prime] = true

    n = prime - 1
    factors = n.factors    
    counter += n if factors.all? { |d| primes[d + n/d] }
end

One also only need the first square root of factors, since larger numbers are paired with the smaller numbers anyway:

(1..Math.sqrt(self) + 1).lazy.select { |n| (self % n).zero? }

This now takes about 100 seconds for n = 100_000_000.

\$\endgroup\$
  • \$\begingroup\$ I'm getting the right answer. Here's the code in full: gist.github.com/Veedrac/1e95a577078410d32de5. \$\endgroup\$ – Veedrac Jun 25 '15 at 8:00
  • \$\begingroup\$ Mine is pretty much word for word? gist.github.com/Aiishe/e82c2681317d41becbeb Let's play find the typo ;) \$\endgroup\$ – Nemo Jun 25 '15 at 8:07
  • \$\begingroup\$ Whatever, I copy/pasted yours and it's working. Didn't find the error in my version. Thanks very much for helping to improve this, and pointing out the mistakes with n.is_a? Prime and my formula, but I don't really understand the reasoning behind your changes, e.g "One can also note that only numbers one below primes actually need to be checked, since 1 is a factor of every number." Is this advanced math or am I really dumb? \$\endgroup\$ – Nemo Jun 25 '15 at 8:19
  • 1
    \$\begingroup\$ @Nemo You wrote n = prime = 1 \$\endgroup\$ – Veedrac Jun 25 '15 at 8:25
  • \$\begingroup\$ @Nemo A number k has a factor 1, so 1 + k/1 must be prime. \$\endgroup\$ – Veedrac Jun 25 '15 at 8:26
0
\$\begingroup\$

You need to use the prime factorization of each number as you check it. You can use the prime factorization of n to quickly produce a list of divisors of n, without testing all numbers from 1 to n.

One common method to do this is to produce an array of ints, A[], with the properties:

  • A[n] <= n
  • if A[n] == n, then n is prime
  • if A[n] < n, then A[n] is a prime factor of n

You can then use A[] to quickly determine if n is prime, and recursively put together its prime factorization if it is not.

\$\endgroup\$
  • 2
    \$\begingroup\$ I don't understand this at all. Could you include an example? \$\endgroup\$ – Nemo Jun 24 '15 at 23:52
  • \$\begingroup\$ It's a basic variation on a prime sieve. \$\endgroup\$ – NovaDenizen Jun 25 '15 at 0:09

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.