CODEWITHSUNDEEP
rubyalgorithmdebuggingprimes
Ciaran
Ciaran

Reputation: 151

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

Upvotes: 1

Views: 411

Answers (1)

advocateofnone
advocateofnone

Reputation: 2541

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

Upvotes: 1

Related Questions