「プロジェクトオイラー問４７」の編集履歴（バックアップ）一覧はこちら
「プロジェクトオイラー問４７」(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つの数を求めよ. その最初の数はいくつか?
解法
篩もどきの処理で片が付きます。
Prologでは篩を効率的に実装する方法がわからないのでためし割りになります。
#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;
}
}
}
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).
