The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

*WARNING: This contains the solution!*

Lots of problems with prime numbers. There are two ways you can solve this problem.

- Lazy way
- Efficient way

The approach for the lazy way is to reuse the code from problem 7 to determine whether a number is a prime. All that is needed is changing a few things around.

#include <iostream>

#include <math.h>

using namespace std;

const int TARGET = 250;

int main()

{

long long primesum = 2;

int primes[TARGET];

primes[0] = 2;

primes[TARGET - 1] = -1;

int number = 3;

int foundCount = 1;

bool isPrime = false;

//sum all primes between 2 and 2,000,000

while (number < 2000000)

{

double max = sqrt((float)number);

//assume a number is prime until proven guilty

isPrime = true;

for (int i = 0; i < foundCount; ++i)

{

//break if the number is divisible by an already found prime number (guilty)

if (number % primes[i] == 0)

{

isPrime = false;

break;

}

//check to see if the square root of the number is less than or equal to the current prime number.

//if so then break. This means the number is a prime.

if (primes[i] >= max)

break;

}

//add the prime number

if (isPrime)

{

primesum += number;

if (foundCount < TARGET)

primes[foundCount++] = number;

}

//increment the number by 2 (to stay odd)

number += 2;

}

cout << "Answer: " << primesum << endl;

}

This lazy method consider every odd number and checks all primes (< sqrt(number) and sees if it is a divisor. This means that these prime numbers are being checked a great deal! The efficient way to do this is instead when a prime is found take every multiple of it within the given range (3 to 2,000,000 in this case) and mark it off as being a composite number. The consequence of this is that each number is only considered once. Afterward simply sum all numbers that are not checked as a composite number. This would be the solution!

Note that we do not need to consider even numbers because 2 is the only prime even number.

The indexing is a little complex and takes some thinking to understand it.

#include <iostream>

#include <math.h>

using namespace std;

const int LIMIT = 1000000;

int main()

{

//an array to keep track of the composite numbers

bool isComposite[LIMIT];

//set all of them equal to false (assume prime until proven guilty)

for (int i = 0; i < LIMIT; ++i)

isComposite[i] = false;

//the max number of index needed to be considered

int max = sqrt((double)LIMIT);

for (int i = 1; i <= max; ++i)

{

//if the number is a prime then mark all multiples of that number as a composite

if (!isComposite[i - 1])

{

for (int j = 2 * i * (i + 1); j <= LIMIT; j += 2 * i + 1)

isComposite[j - 1] = true;

}

}

//2 is a prime

long long primesum = 2;

//check all numbers. if one is a prime then add it

for (int i = 1; i <= LIMIT; ++i)

if (!isComposite[i - 1])

primesum += 2 * i + 1;

cout << "Answer: " << primesum << endl;

}

This solution is much more efficient and scales much better than the lazy method. Pretty cool huh?

*saved game*

## No comments:

## Post a Comment