Euler Solution 50

From ProgSoc Wiki

Jump to: navigation, search

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?

Solutions for Problem 50

Python by Althalus

Runtime: 6 seconds

import time, math
start_time = time.time()

def isPrime(num):
        for i in range(2,int(math.sqrt(num))+1):
                if (num%i) == 0:
                        return False
        return True

#Start prime number generator
#We'll start with 100 attempts to get primes. If that's not enough, I'll up it.
primes = [2,3,5]
for i in range(1,1000):
        if isPrime(6*i+1):
                primes.append(6*i+1)
        if isPrime(6*i+5):
                primes.append(6*i+5)
primes.sort()

num=0
curnum=0
consecutive=0
curcon=0
#we have a thousand elements in our array. The answer won't necessarily start with the first prime...
for k in range(0,1000):
        curcon=0
        curnum=0
        #Trim off any values already used as a starting point....
        for i in primes[k:]:
                if(curnum+i >= 1000000):
                        break
                curnum += i
                curcon += 1
                if isPrime(curnum) and curcon>consecutive:num,consecutive=curnum,curcon
        
print (num)
run_time = time.time() - start_time
print (run_time)
Personal tools