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\$
3
  • \$\begingroup\$ Precompute primes. \$\endgroup\$
    – Veedrac
    Commented Jun 24, 2015 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
    Commented Jun 24, 2015 at 21:47
  • 1
    \$\begingroup\$ Have you tested if for smaller values, at least? It seems to always return 0. \$\endgroup\$
    – Veedrac
    Commented Jun 25, 2015 at 4:53

2 Answers 2

4
\$\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\$
8
  • \$\begingroup\$ I'm getting the right answer. Here's the code in full: gist.github.com/Veedrac/1e95a577078410d32de5. \$\endgroup\$
    – Veedrac
    Commented Jun 25, 2015 at 8:00
  • \$\begingroup\$ Mine is pretty much word for word? gist.github.com/Aiishe/e82c2681317d41becbeb Let's play find the typo ;) \$\endgroup\$
    – Nemo
    Commented Jun 25, 2015 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
    Commented Jun 25, 2015 at 8:19
  • 1
    \$\begingroup\$ @Nemo You wrote n = prime = 1 \$\endgroup\$
    – Veedrac
    Commented Jun 25, 2015 at 8:25
  • \$\begingroup\$ @Nemo A number k has a factor 1, so 1 + k/1 must be prime. \$\endgroup\$
    – Veedrac
    Commented Jun 25, 2015 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
  • 2
    \$\begingroup\$ I don't understand this at all. Could you include an example? \$\endgroup\$
    – Nemo
    Commented Jun 24, 2015 at 23:52
  • \$\begingroup\$ It's a basic variation on a prime sieve. \$\endgroup\$ Commented Jun 25, 2015 at 0:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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