下から素数の和を積み上げて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