「プロジェクトオイラー問４７」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー問４７ - (2014/02/17 (月) 10:55:23) のソース

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

Problem 47 「異なる素因数」 †
それぞれ2つの異なる素因数を持つ連続する2つの数が最初に現れるのは:

14 = 2 × 7
15 = 3 × 5

それぞれ3つの異なる素因数を持つ連続する3つの数が最初に現れるのは:

644 = 2＾2 × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19

最初に現れるそれぞれ4つの異なる素因数を持つ連続する4つの数を求めよ. その最初の数はいくつか?




解法
C++なら篩もどきの処理で片が付きます。
Prologでは篩を効率的に実装する方法がわからないのでためし割りになります。


C++

 #include<stdio.h>
 
 const int MAX=200000;
 int main(){
 	int count[MAX]={0};
 	for(int i=2;i<MAX;i++){
 		if(count[i]!=0)continue;
 		for(int j=i;j<MAX;j+=i){
 			count[j]++;
 		}
 	}
  	for(int i=0;i<MAX-4;i++){
 		if(count[i]==4&&count[i+1]==4&&count[i+2]==4&&count[i+3]==4){
 			printf("%d\n",i);
 			break;
 		}
 	}
 }




Prolog
全部試し割る力づくの解法


 divs(N,P,N):-N mod P>0,!.
 divs(N,P,Result):-
 	N1 is N//P,
 	divs(N1,P,Result).
 
 count_fact(N,P,Result):-
 	N<P*P,
 	!,
 	(N>1 -> Result is 1;Result is 0).
 count_fact(N,P,Result):-
 	N mod P=:=0,
 	!,
 	divs(N,P,N1),
 	P1 is P+1,
 	count_fact(N1,P1,Re),
 	Result is Re+1.
 count_fact(N,P,Result):-
 	!,
 	P1 is P+1,
 	count_fact(N,P1,Result).
 
 search([4,4,4],N,Result):-
 	count_fact(N,2,CF),
  	CF=:=4,
 	!,
 	Result is N-3.
 search([_,CF2,CF3],N,Result):-
 	!,
  	count_fact(N,2,CF4),
 	N1 is N+1,
 	search([CF2,CF3,CF4],N1,Result).
 
 main47:-
 	search([0,1,1],4,Ans),write(Ans).