Euler 357 solution efficiency 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.
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 &gt; 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 &gt; 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.