-
Notifications
You must be signed in to change notification settings - Fork 0
/
problem50.py
68 lines (44 loc) · 1.45 KB
/
problem50.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#!-*-coding=utf8 -*-
import time
"""
========================
Project Euler Problem 50
========================
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 ero_sieve(n):
primes=set(i for i in xrange(3,n+1,2))
for i in set(primes):
j=2
while i*j<n:
primes.discard(i*j)
j+=1
primes.add(2)
return primes
def problem50():
primes=list(ero_sieve(1000000))
most_consec=int()
most_consec_sum=int()
for i in primes[:len(primes)/2]:
prime_sum=i
n=primes.index(i)+1
count=0
while prime_sum + primes[n] <1000000:
prime_sum+=primes[n]
if count>most_consec:
if prime_sum in primes:
most_consec=count
most_consec_sum = prime_sum
print most_consec_sum
n+=1
count+=1
return most_consec_sum, most_consec
if __name__ == '__main__':
time1=time.time()
print problem50()
time2=time.time()
print time2-time1