Project Euler 50

素数41は6つの連続する素数の和として表せる:

41 = 2 + 3 + 5 + 7 + 11 + 13.
100未満の素数を連続する素数の和で表したときにこれが最長になる.

同様に, 連続する素数の和で1000未満の素数を表したときに最長になるのは953で21項を持つ.

100万未満の素数を連続する素数の和で表したときに最長になるのはどの素数か?

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2050

#include <iostream>
#include <deque>
using namespace std;

//素数を max まで計算する
deque<bool> p;
deque<int> prime;
void calc_prime(const int max){
	for(int i=0 ; i<max+1 ; i++){
		p.push_back(true);
	}
	p[0] = false;
	p[1] = false;

	double myEnd = sqrt(double(max));
	for(int i=2 ; i < myEnd ; i++){
		for(int j=2 ; i*j<=max ; j++){
			p[i*j] = false;
		}
	}

	for(int i=2 ; i<=max ; i++){
		if(p[i]) prime.push_back(i);
	}
}

int main(){

	calc_prime(1000000);

	int n=0, max=0, maxnum=0;

	for(int i=0 ; i<prime.size()-1 ; i++){
		n = prime[i];
		for(int j=1 ; ; j++){
			n += prime[i+j];
			if(n>1000000) break;

			if(p[n] && max<j+1){
				max = j+1;
				maxnum = n;
				//cout << maxnum << endl;
			}
		}
	}
	cout << maxnum << endl;
}

特にコメントすることがないなぁ・・・30分弱ぐらいでできました。