Prime number 41 can be expressed as the sum of six consecutive prime numbers:
41 = 2 + 3 + 5 + 7 + 11 + 13.
This is the longest when a prime number less than 100 is represented by the sum of consecutive prime numbers.
Similarly, when the sum of consecutive prime numbers represents a prime number less than 1000, the longest is 953, which has 21 terms.
Which prime number is the longest when expressing a prime number less than 1 million as the sum of consecutive prime numbers?
I solved it as follows.
pri ['list']pri ['list'] [i] of a certain starting point.import mymath
def main():
MAX = 10**6
pri = mymath.get_primes(MAX)
pri_length = len(pri['list'])
i, c_max, ans = 0, 0, 0
while i < pri_length:
s, j, c = pri['list'][i], i + 1, 1
while j < pri_length and s + pri['list'][j]< MAX:
s += pri['list'][j]
c += 1
if pri['bool'][s] and c_max < c:
ans, c_max = s, c
j += 1
i += 1
print ans
main()
Recommended Posts