Project Euler 50

• 問題

Problem 50：Consecutive prime sum
The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13
This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

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

• 解答例

def primeNum(num):
    prime = [2]
    i = 3
    while len(prime) < num:
        for n in prime:
            if i % n == 0:
                break
        else:
            prime.append(i)
        i += 2
    return prime[-1]

def sieveEratosthenes(num):
    isPrime = [True] * (num + 1)
    isPrime[0] = False
    isPrime[1] = False
    primes = []
    for i in range(2, (num + 1)):
        if isPrime[i]:
            primes.append(i)
            for j in range(2 * i, (num + 1), i):
                isPrime[j] = False
    return primes

def isPrime(num):
    if num <= 1:
        return False
    elif num == 2 or num == 3:
        return True
    if num % 2 == 0 or num % 3 == 0:
        return False
    if not(num % 6 == 1) and not(num % 6 == 5):
        return False
    i = 5
    while i * i <= num:
        if num % i == 0 or num % (i + 2) == 0:
            return False
        i += 6
    return True

temp = 0
i = 1
while temp < 1000000:
    temp += primeNum(i) 
    i += 1
prime = sieveEratosthenes(primeNum(i - 2))

# 前の要素から削る
temp1 = sum(prime)
prime1 = list(prime)
for p in prime:
    temp1 -= p
    prime1.pop(0)
    if isPrime(temp1):
        break

# 後ろの要素から削る
temp2 = sum(prime)
prime = prime[::-1]
prime2 = list(prime)
for p in prime:
    temp2 -= p
    prime2.pop(0)
    if isPrime(temp2):
        break

# 結果を出力
if len(prime1) > len(prime2):
    print(temp1, prime1)
else:
    print(temp2, prime2)