Find the sum of all the primes below two million.
#Find the sum of all the primes below two million.
from math import sqrt
import time
#this function will determine if
# num is prime
def nextPrime(num):
isPrime = False
while not isPrime:
numSqrt = sqrt(num)
isPrime = True
i = 2
while i <= numSqrt and isPrime:
if num % i == 0:
isPrime = False
i += 1
if not isPrime:
num += 1
return num
curNum = 2
MAX_NUM = 2000000
sumOfPrimes = 0
startTime = time.time()
print "Calculating the sum of primes below %d" % (MAX_NUM,)
while True:
#Only check odd numbers that are greater than 2
curNum = nextPrime(curNum)
if curNum < MAX_NUM:
sumOfPrimes += curNum
else:
break
if curNum <= 2:
curNum +=1
else:
curNum += 2
endTime = time.time()
print 'calculation took %0.3f ms' % ((endTime-startTime)*1000.0,)
print "The sum of all primes below %d is %d" % (MAX_NUM,sumOfPrimes)
Some pretty straighforward code here. To check for primes, I'm only checking until the square root of the number. If you don't find any factors before getting to the square root, you won't find any factors. Also, I'm making sure that I'm only checking 2, and the odd numbers. I'm sure there's faster ways to find prime numbers, but this is reasonably fast. I also put in some code to time how long it took my code to run.