Euler 357 solution efficiency

Question

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.

Answer 1

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.

Answer 2

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.