Last active
August 29, 2015 14:12
-
-
Save ebartrum/105927fc3571f646e85e to your computer and use it in GitHub Desktop.
A solution to the 10th Project Euler problem
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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