Skip to content

Instantly share code, notes, and snippets.

@jakedobkin
Created December 11, 2011 02:16
Show Gist options
  • Select an option

  • Save jakedobkin/1457748 to your computer and use it in GitHub Desktop.

Select an option

Save jakedobkin/1457748 to your computer and use it in GitHub Desktop.
Euler 50
# set up prime sieve to n- track running sum in separate sum array
total = 0
n=1000000
myPrimes = [True]*(n+1)
mySum = [0]*(n+1)
last = 0
for i in range (2,n):
if myPrimes[i] == True:
j = 2*i
while j<=n:
myPrimes[j]=False
j=j+i
mySum[i]=last+i
last = mySum[i]
# notice that after mySum[3943], you've gone over a million- it's composite.
# so start there and subtract the lowest sum, mySum[2]
# if it's prime and below 1MM, stop- if it's not, try subtracting mySum[3]...
s = set()
for l in range (3900,3943):
for k in range (2,100):
if myPrimes[mySum[k]]!=True:
test = mySum[l]-mySum[k]
if myPrimes[test] == True:
s.add(test)
print max(s)
@jakedobkin
Copy link
Author

Still a little manual- but it does run in about 2s, as opposed to 55s for the last version. And you could do it for any length n- simply by looking up what number the sum goes over n at.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment