Skip to content

Instantly share code, notes, and snippets.

@ebartrum
Last active August 29, 2015 14:12
Show Gist options
  • Save ebartrum/105927fc3571f646e85e to your computer and use it in GitHub Desktop.
Save ebartrum/105927fc3571f646e85e to your computer and use it in GitHub Desktop.
A solution to the 10th Project Euler problem
#Define a function which checks if any members of x divide y (If so return True, otherwise False) but only checks up to the squareroot of y (This greatly improves efficiency).
#In other words if the function finds a member of x that is >= the sqrt of y it stops looking and returns the current state (ans)
def divis(x,y):
ans=False
for z in x:
if y%z==0:
ans=True
break
if z>=y**0.5+1:
break
return ans
#Define a generator to generate primes:
def primeGenerator():
yield 2
primes=[2]
n=3
while True:
if divis(primes,n):
n+=2
else:
yield n
primes.append(n)
n+=2
def sumNPrimes(n):
x=primeGenerator()
currentPrime=next(x)
ans=currentPrime
while currentPrime<n:
currentPrime=next(x)
if currentPrime<n:
ans+=currentPrime
return ans
print("sumNPrimes(3):"+str(sumNPrimes(3)))
print("sumNPrimes(5):"+str(sumNPrimes(5)))
print("sumNPrimes(7):"+str(sumNPrimes(7)))
print("sumNPrimes(11):"+str(sumNPrimes(11)))
print("sumNPrimes(2000000):"+str(sumNPrimes(2000000)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment