Grind Report 11

Problem 10

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.

1. Lazy way
2. Efficient way

I started with the lazy 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*