Ciaran S - 3 months ago 22

Ruby Question

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`

`N = 100`

`N = 1000`

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`

.

Source (Stackoverflow)

Comments