Kibbee.ca
icon
Project Euler: Problem 10

Find the sum of all the primes below two million.

[Full Question]

#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)

[Download Code]

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.

No Comments Posted