Ciaran S Ciaran S - 3 months ago 22
Ruby Question

Project Euler #50 - Consecutive prime sum - Ruby

I'm trying to solve Project Euler problem #50 (https://projecteuler.net/problem=50) where the problem is defined as:


Which prime, below one-million, can be written as the sum of the most
consecutive primes?


I've come up with two different solutions both giving the same wrong answer which leads me to believe the error happens as I'm building my list of primes, however, I can't seem to find any error. My solutions also seem to work for
N = 10
and
N = 100
but not
N = 1000
. Any help is appreciated.

Solution 1: (output = 958577)

require 'Prime'

# Initialising primes
N = 1_000_000
primes = {}

(2..N).each do |i|
primes[i] = true
end

i = 2

while i * i <= N
if primes[i]
j = i
while i * j <= N
primes[i * j] = false
j += 1
end
end
i += 1
end

# New prime list where total sum is less than N
new_primes = []
i = 2
sum = 0

while sum + i < N
if primes[i]
new_primes << i
sum += i
end
i += 1
end

# Keep removing last prime from list until total sum is prime
while true
if Prime.prime?( new_primes.inject(0, :+) )
puts new_primes.inject(0, :+)
break
else
new_primes.delete_at(-1)
end
end


Solution 2: (output = 958577)

require 'Prime'

# Initialising primes
N = 1_000_000
primes = {}

(2..N).each do |i|
primes[i] = true
end

i = 2

while i * i <= N
if primes[i]
j = i
while i * j <= N
primes[i * j] = false
j += 1
end
end
i += 1
end


sum = 0
max = 0
i = 2

while i < N
if primes[i]
sum += i
if sum < N && Prime.prime?(sum)
max = sum
end
end
i += 1
end

puts max

Answer

(w.r.t to Solution 2) Your method to find primes seems correct. The problem is with your logic. If the primes less than N are p_1,p_2,..,p_k, then you are only considering only the sums p_1, p_1+p_2, p_1+p_2+p_3,...,p_1+p_2+..+p_k. What about sums not starting from p_1, say p_3+p_4.

Comments