The Prime 41 (3)

ThePrime41_3.cpp

#include <iostream>
#include <type_traits>

using namespace std;

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

int minIndex = 0;
int maxIndex = 0;
int maxSum = 0;

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()
{
	cout << primes[minIndex] << " + ... + " << primes[maxIndex] << " = " << maxSum << " : " << maxIndex - minIndex + 1 << endl;
}

int main()
{
	FillPrimes();

	int lengthFrom2 = 1;
	int sumFrom2 = 2;

	for (int i = 1; i < primeCount; i++)
	{
		int newSum = sumFrom2 + primes[i];
		if (newSum >= Max) break;

		lengthFrom2++;
		sumFrom2 = newSum;
	}

	for (int length = lengthFrom2; length > 0; length--)
	{
		int newSum = sumFrom2;
		for (int i = 0; i < primeCount; i++)
		{
			if (i > 0)
			{
				newSum = newSum - primes[i - 1] + primes[i + lengthFrom2 - 1];
			}
			if (newSum >= Max)
			{
				sumFrom2 -= primes[--lengthFrom2];
				break;
			}
			else if (isPrime[newSum])
			{
				if (maxSum == 0)
				{
					minIndex = i;
					maxIndex = i + lengthFrom2 - 1;
					maxSum = newSum;
					PrintResult();
					return 0;
				}
			}
		}
	}

	return 0;
}