Paradigm X

paradigm_x_3

// Problem: Given that 2011 is both a prime number and 
// a sum of 11 consecutive prime numbers,
// find the immediate next number that satisfies both conditions.
#include <iostream> 
#include <cstdio>
#define MAX_NUMBER 1000000
#define TARGET_NUMBER 2011
using namespace std;

int primeTable[MAX_NUMBER];
int primeSequence[MAX_NUMBER];

void genPrimeTable()
{
    int base = 2, newBase = 2;
    while (base < MAX_NUMBER)
    {
        for (int i = base + base; i < MAX_NUMBER; i += base)
        {
            primeTable[i] = 1;
        }
        newBase = base;
        for (int i = base + 1; i < MAX_NUMBER; i++)
        {
            if (primeTable[i] == 0)
            {
                newBase = i;
                break;
                }
        }
        if (base == newBase)
            break;
        else
            base = newBase;    
    }
}

void genPrimeSequence()
{
    int pos = 0;
    for (int i = 2; i < MAX_NUMBER; i++)
    {
        if (primeTable[i] == 0)
        {
            primeSequence[pos++] = i;
        }
    }
}

int work()
{
    // enumerate the running sum of 11 adjacent prime numbers until 2011 is reached
    int sum = 0, pos = 0;
    for (pos = 0; pos < 11; pos++)
        sum += primeSequence[pos];
    while (sum < TARGET_NUMBER)
    {
        sum += primeSequence[pos] - primeSequence[pos - 11];
        pos++;

    }
    // Keep on enumerating until a prime sum is found.
    sum += primeSequence[pos] - primeSequence[pos - 11];
    pos ++;
    while (primeTable[sum] == 1)
    {
        if (primeSequence[pos] == 0){
            break;
            }
        sum += primeSequence[pos] - primeSequence[pos - 11];
        pos++;
    }
    if (primeSequence[pos] == 0)
        printf("No solution\n");
    else    
        printf("The answer is %d\n", sum);
}
        
int main()
{
    genPrimeTable();  
    genPrimeSequence();
    work();
    return 0;
}