※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。


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).