Problem 50(Consecutive prime sum)

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?

 

In Python:

import time
import math

def isprime(n):
    if n == 0 or n == 1:
        return False
    else:
        for i in range(2, int(math.sqrt(n)) + 1):
            if n % i == 0:
                return False
        return True

def seive(n):
    primeList = []
    pcodeList = [1 for i in range(0, n)]
    pcodeList[0] = 0
    for i in range(2, n + 1):
        if pcodeList[i - 1] == 1:
            primeList.append(i)
            for j in range(2, (n // i) + 1):
                pcodeList[i * j - 1] = 0
    return primeList

startTime = time.time()
primeList = seive(10 ** 6)
total = 0
count = 0
resultList = []
countList = []
for i in range(0, len(primeList) - 1):
    count = 0
    if i == 0:
        total = 0
        j = i
        while total < 10 ** 6 and j < len(primeList) - 1:
            total += (primeList[j] + primeList[j + 1])
            count += 1
            j += 2
            if isprime(total) and total < 10 ** 6:
                resultList.append(total)
                countList.append(count)
    else:
        total = primeList[i]
        j = i + 1
        while total < 10 ** 6 and j < len(primeList) - 1:
            total += (primeList[j] + primeList[j + 1])
            count += 1
            j += 2
            if isprime(total) and total < 10 ** 6:
                resultList.append(total)
                countList.append(count)

print(resultList[countList.index(max(countList))], max(countList))
print(time.time() - startTime, "seconds")

Run time: 6.135763883590698 seconds

 

In Python:

import time
import math

def isprime(n):
    if n == 0 or n == 1:
        return False
    else:
        for i in range(2, int(math.sqrt(n)) + 1):
            if n % i == 0:
                return False
        return True

def seive():
    n = 10 ** 6
    i = 2
    total = 0
    primeList = []
    pcodeList = [1 for i in range(0, n)]
    pcodeList[0] = 0
    while total < 10 ** 6:
        if pcodeList[i - 1] == 1:
            primeList.append(i)
            total += i
            for j in range(2, (n // i) + 1):
                pcodeList[i * j - 1] = 0
        i += 1
    return primeList[0: i - 1]

startTime = time.time()
primeList = seive()
total = 0
maxcount = 0
result = 0
for i in range(len(primeList) - 1):
    total = primeList[i]
    j = i + 1
    while total < 10 ** 6 and j < len(primeList) - 1:
        total += primeList[j]
        if isprime(total) and total < 10 ** 6:
            if j - i + 1 > maxcount:
                maxcount = j - i + 1
                result = total
        j += 1
print(result, maxcount)
print(time.time() - startTime, "seconds")

Run time: 1.1931350231170654 seconds

 

Solution: 997651