「プロジェクトオイラー問５０」の編集履歴（バックアップ）一覧はこちら

「プロジェクトオイラー問５０」(2014/02/18 (火) 12:43:15) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

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

*Problem 50 「連続する素数の和」 †
素数41は6つの連続する素数の和として表せる:

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

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

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





解法
B<Aとして
A番目の素数までの集計値-B番目の素数までの集計値の差分が
AからBまでの連続した素数の和です。
それだけの問題です。
素数は篩で選り分けて集計して。
後は差分のなかで素数となるものを全部検証するだけです。



 #include<stdio.h>
 #include<string.h>
 #include<vector>
 const int MAX=1000*1000;
 
 std::vector<__int64> sums;
 bool isPrime[MAX];
 
 void setPrime(){	
 	memset(isPrime,true,sizeof(isPrime));
 	isPrime[0]=isPrime[1]=false;
 	for(int i=2;i*i<MAX;i++){
 		if(isPrime[i]==false)continue;
 		int add=(i%2==0?2:i*2);
 		int s=(i%2==0?4:i*3);
 		for(int j=s;j<MAX;j+=add){
 			isPrime[j]=false;
 		}
 	}
 	__int64 sum=0;
 	sums.push_back(0);
  	for(int i=2;i<MAX;i++){
 		if(isPrime[i]){
 			sum+=i;
 			sums.push_back(sum);
 		}
 	}
 }
 
 int main(){
  	setPrime();
	int ansLen=0,ansPrime=0;
 	for(int i=1;i<sums.size();i++){
 		for(int j=i-1;j>=0;j--){
 			int sa=sums[i]-sums[j];
 			if(sa>=MAX)break;
 			if(isPrime[sa]&&ansLen<i-j){
 				ansPrime=sa;
 				ansLen=i-j;
 			}
		}
  	}
 	printf("%d %d\n",ansPrime,ansLen);
 }

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

*Problem 50 「連続する素数の和」 †
素数41は6つの連続する素数の和として表せる:

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

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

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





解法
B<Aとして
A番目の素数までの集計値-B番目の素数までの集計値の差分が
AからBまでの連続した素数の和です。
それだけの問題です。
素数は篩で選り分けて集計して。
後は差分のなかで素数となるものを全部検証するだけです。
問題の例より差分は21個以上と分かっていますからそこで少し計算量を稼ぎます。


 #include<stdio.h>
 #include<string.h>
 #include<vector>
 const int MAX=1000*1000;
 
 std::vector<__int64> sums;
 bool isPrime[MAX];
 
 void setPrime(){	
 	memset(isPrime,true,sizeof(isPrime));
 	isPrime[0]=isPrime[1]=false;
 	for(int i=2;i*i<MAX;i++){
 		if(isPrime[i]==false)continue;
 		int add=(i%2==0?2:i*2);
 		int s=(i%2==0?4:i*3);
 		for(int j=s;j<MAX;j+=add){
 			isPrime[j]=false;
 		}
 	}
 	__int64 sum=0;
 	sums.push_back(0);
  	for(int i=2;i<MAX;i++){
 		if(isPrime[i]){
 			sum+=i;
 			sums.push_back(sum);
 		}
 	}
 }
 
 int main(){
  	setPrime();
	int ansLen=0,ansPrime=0;
 	for(int i=1;i<sums.size();i++){
 		for(int j=i-20;j>=0;j--){
 			int sa=sums[i]-sums[j];
 			if(sa>=MAX)break;
 			if(isPrime[sa]&&ansLen<i-j){
 				ansPrime=sa;
 				ansLen=i-j;
 			}
		}
  	}
 	printf("%d %d\n",ansPrime,ansLen);
 }