Ciaran S - 1 year ago 85
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
``````

(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`.