欧拉计划 #50 - 连续素数和 - Ruby

Question

我正在尝试解决 Project Euler 问题 #50 (https://projecteuler.net/problem=50)，其中问题定义为：

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

我想出了两种不同的解决方案，都给出了相同的错误答案，这让我相信错误发生在我构建素数列表时，但是，我似乎找不到任何错误。我的解决方案似乎也适用于 N = 10 和 N = 100，但不适用于 N = 1000。感谢任何帮助。

解决方案 1：（输出 = 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

解决方案 2：（输出 = 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 1

(w.r.t to Solution 2) 你寻找素数的方法似乎是正确的。问题出在你的逻辑上。如果小于N的素数是p_1,p_2,..,p_k，那么你只考虑只有总和 p_1、p_1+p_2、p_1+p_2+p_3、...、p_1+p_2+..+p_k。不从 p_1 开始的总和呢，比如说 p_3+p_4.

欧拉计划 #50 - 连续素数和 - Ruby

Project Euler #50 - Consecutive prime sum - Ruby

ruby

algorithm

debugging

primes