Will Clausen's Website

Categories
WCW

Project Eurler Problem 10

Here’s the problem:

Find the sum of all primes less than 2,000,000

projecteuler.net/problem=10

My solution:


# Author: Will Clausen
#
# Date: Jan 7, 2013
#
# This program will solve Problem 10 from Project Euler.
# The code is basically the same as the code for Problem 7.

import math

# Find the sum of all the primes below two million
def problem10():
	# 2 is the first prime number, so start there
	sum = 2
	
	# The next number to check is 3
	num = 3

	# While there are still numbers to check
	while num < 2000000:
		# If the number is prime
		if isPrime(num):
			# Add the number to the total
			sum += num
		
		# And increment by 2 (since even numbers above 2 aren't prime)
		num += 2

	return sum

# Simple function to determine if a number is prime. Not super fast,
# but will work for this problem because the numbers aren't super huge.
def isPrime(Num):
	# Bound for divisors to check
	sqrtNum = int(math.sqrt(Num)) + 1
	
	# Only need to check if the number is divisible by odd numbers, so
	# do that in the range function
	for x in range(3, sqrtNum, 2):
		if Num % x == 0:
			return False

	return True

Leave a Reply

Your email address will not be published. Required fields are marked *