Project Euler Problem 10

December 23, 2011

I’ve been having some fun doing the first few problems of Project Euler and figured I’d share my solution to problem 10 here.

The Problem
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.

The Solution
My solution is fairly simple, testing primality for all the numbers below 2,000,000. If prime, adding them to a running total.

/**
 * Calculate the sum of all the primes below two million. 
 **/
#include 
#include 
using namespace std;

bool isPrime(long num) {
	if(num<=1)
		return false;
	for(long i=2; i<=sqrt(num*1.0); i++)
	{
		if(num%i==0)
			return false;
	}
	return true;
}

int main () {
	long upperlimit = 2000000, sum = 0;

	for (long i = 2; i < upperlimit; i++) {
		if(isPrime(i)) {
			sum += i;
			cout << "Prime found: " << i << endl;
		}
	}

	cout << "The sum of primes below " << upperlimit << " is " << sum << endl;

	return (0);
}

The interesting part of this problem for me was I updated my primality test to include the fact that if a number n has a factor greater than sqrt(n) it must also have one less than sqrt(n), so we only have to test up to sqrt(n) in our primality test:

bool isPrime(long num) {
	if(num<=1)
		return false;
	for(long i=2; i<=sqrt(num*1.0); i++)
	{
		if(num%i==0)
			return false;
	}
	return true;
}

Author

Stay in Touch!

Stay in Touch!
Solutions Architecture

browse through our blog articles

Blog Archive