The prime 41

ThePrime41.cpp

#include <iostream>
#include <type_traits>

using namespace std;

const int Max = 1000;
bool isPrime[Max];
int primes[Max] = { 0 };
int primeCount = 0;

int minIndex = 0;
int maxIndex = 0;
int seqIndex = 0;
int sums[Max][Max] = { 2 };

void FillPrimes()
{
	isPrime[0] = false;
	isPrime[1] = false;
	for (int i = 2; i < Max; i++)
	{
		isPrime[i] = true;
	}

	for (int i = 2; i < Max; i++)
	{
		if (isPrime[i])
		{
			for (int j = i * 2; j < Max; j += i)
			{
				isPrime[j] = false;
			}
		}
	}

	for (int i = 2; i < Max; i++)
	{
		if (isPrime[i])
		{
			primes[primeCount++] = i;
		}
	}
}

void PrintResult()
{
	for (int i = minIndex; i < maxIndex; i++)
	{
		cout << primes[i] << " + ";
	}
	cout << primes[maxIndex] << " = " << sums[minIndex][maxIndex] << endl;
}

void SetSum(int first, int last, int sum)
{
	sums[first][last] = sum;
	if (isPrime[sum] && ((last)-(first)) > (maxIndex - minIndex))
	{
		minIndex = first;
		maxIndex = last;
		PrintResult();
	}
}

int main()
{
	FillPrimes();

	for (int i = 1; i < primeCount; i++)
	{
		int prime = primes[i];
		int sum = sums[seqIndex][i - 1] + prime;

		while (sum >= Max)
		{
			sum -= primes[seqIndex];
			seqIndex++;
		}

		if (seqIndex == i)
		{
			int newSum = prime;
			SetSum(seqIndex, i, newSum);
		}
		else
		{
			{
				int newSum = prime + sums[seqIndex][i - 1];
				SetSum(seqIndex, i, newSum);
			}

			for (int j = seqIndex; j < i; j++)
			{
				int newSum = sums[seqIndex][i] - sums[seqIndex][j];
				SetSum(j + 1, i, newSum);
			}
		}
	}

	PrintResult();

	return 0;
}