1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94
|
/* Project Euler #050
The prime 41, can be written as the sum of six consecutive
primes:
41 = 2 + 3 + 5 + 7 + 11 + 13
This is the longest sum of consecutive primes that adds to
a prime below one-hundred.
The longest sum of consecutive primes below one-thousand
that adds to a prime, contains 21 terms, and is equal to 953.
Which prime, below one-million, can be written as the sum
of the most consecutive primes?
*/
/* Thoughts
The key terms here are "consecutive primes". This makes it
much easier, because it just means that we have to keep
adding primes in sequence and then check if the sum is a
prime, and if so, how close it is to a million.
We will also need to check consecutive primes that don't
start with a two though.
*/
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std;
int main()
{
vector<long> Primes;
const unsigned long long limit = 1000000;
unsigned long i = 2;
bool *IsPrime = new bool[limit];
memset(IsPrime, true, sizeof(bool) * limit);
IsPrime[0] = IsPrime[1] = false;
while (i < limit)
{
Primes.push_back(i);
for (unsigned long j = i; j * i < limit; j++)
{
IsPrime[i*j] = false;
}
if (i == 2)
{
i = 3;
}
else
{
do
{
i += 2;
} while (!IsPrime[i] && i < limit);
}
}
delete(IsPrime);
unsigned long max_count = 0, max_prime = 0;
for (i = 0; i < 100; i++)
{
unsigned long j, sum = 0, count = 0, prime = 0;
for (j = i; sum + Primes[j] < 1000000; j++)
{
sum += Primes[j];
if (find(Primes.begin(), Primes.end(), sum) != Primes.end())
{
count = j - i;
prime = sum;
}
}
if (count > max_count)
{
max_count = count;
max_prime = prime;
}
}
cout << max_prime << ", composed of " << max_count << " consecutive primes." << endl;
cout << "Program run-time is " << clock() / CLOCKS_PER_SEC << " seconds." << endl;
return 0;
}
| |