Problem #46

For this one, all I did was create an array of bools all the way up to 10000 that sets every number to false, then loops through every possibility of adding primes with two times a square, it then sets that value in the array to true. Then just checks for an odd number that is still false in the array. The first one must be what we are looking for.

#include <iostream>
#include <ctime>
#include <string>
#include <cmath>

#define MAX    10000

using namespace std;

int getNextPrime (int);
bool isPrime (int);

int main() 
{
    clock_t start = clock();
    long long int total = 0;
    bool numbers[MAX];

    for (int i = 0; i < MAX; i++)
        numbers[i] = false;

    for (int i = 1; ;i = getNextPrime (i))
    {
        if (i > MAX - 1)
            break;

        for (int j = 0; ;j++)
            if (i + 2 * j * j > MAX)
                break;
            else
                numbers[i + 2 * j * j] = true;
    }
    
    for (int j = 10; j < MAX; j++)
        if (numbers[j] == false)
            if (j % 2 == 1)
            {
                total = j;
                break;
            }

    cout << total << endl 
         << "Process took " << (static_cast<double> (clock()) - start) / CLOCKS_PER_SEC << " seconds." << endl;

    system("pause");
    return 0;
}

int getNextPrime (int num)
{
    int holder = 0;

    for (int i = num + 1; ;i++)
        if (isPrime (i))
            return i;
}

bool isPrime (int num)
{
    if (num <= 1)
        return false;
  
    if (num == 2 || num == 3)
        return true;

    for (unsigned int i = 2; i < static_cast<int> (sqrt (static_cast<double> (num))) + 1; i++)
        if (num % i == 0)
            return false;
   return true;
}