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*
