プロジェクトオイラー問50

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2050
Problem 50 「連続する素数の和」 †
連続する素数の和で表せる素数のうち素数和の長さが最長になるものを答えよ。

下から素数の和を積み上げてmemoに蓄え、素数和の長さを長いほうから調べ、積み上げ上-積み上げ下が素数ならそれが答え。
当然計算量をとる要素が見当たらないので、ほぼ0セコンド。

#include<stdio.h>
#include<vector>
const int LIMIT=1000*1000;
bool not_prime[LIMIT]={1,1,0};
std::vector<int> memo;
int main(){
	for(int i=2;i*i<LIMIT;i+=1+(i&1)){
		if(not_prime[i]==true)continue;
		int start=4,add=2;
		
		if(i%2==1){
			start=i*3;
			add=i*2;
		}
		for(int j=start;j<LIMIT;j+=add){
			not_prime[j]=true;
		}
	}
	int num=2;
 	memo.push_back(0);
 	memo.push_back(2);
	for(int i=3;i<LIMIT;i+=2){
		if(not_prime[i]==false){
			if(num+i>=LIMIT)break;
			num+=i;
 			memo.push_back(num);
		}
	}
	int len=memo.size()-1;
	while(len>0){
		for(int i=0;i+len<memo.size();i++){
			int num=memo[i+len]-memo[i];
 			if(not_prime[num]==false){
				printf("%d",num);
				return 0;
 			}
		}
		len--;
	}
}
最終更新:2014年12月07日 09:04