# 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.

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

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.

• I'm getting the right answer. Here's the code in full: gist.github.com/Veedrac/1e95a577078410d32de5. – Veedrac Jun 25 '15 at 8:00
• Mine is pretty much word for word? gist.github.com/Aiishe/e82c2681317d41becbeb Let's play find the typo ;) – Nemo Jun 25 '15 at 8:07
• 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? – Nemo Jun 25 '15 at 8:19
• @Nemo You wrote n = prime = 1 – Veedrac Jun 25 '15 at 8:25
• @Nemo A number k has a factor 1, so 1 + k/1 must be prime. – Veedrac Jun 25 '15 at 8:26

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.

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