プロジェクトオイラーの問題をPrologで解く。 問い1 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%201 数式で解くのが正しいけれどまあいいか。 mod_n(N,15,N):-0=:=N mod 15,!. mod_n(N,5,N):-0=:=N mod 5,!. mod_n(N,3,N):-0=:=N mod 3,!. mod_n(_,_,0). calc(1000,Sum):-write(Sum). calc(N,Sum):-mod_n(N,_,Add),Sum1 is Sum+Add,N1 is N+1,calc(N1,Sum1). 問い2 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%202 まあ少しくらいの工夫はする。 マクローリン展開を使う方法は私には理解できなかった。 fina(_,_,F,Sum):-F>=4000000,write(Sum),!. fina(A,B,F,Sum):-B1 is 2*A+3*B, A1 is F,F1 is A1+2*B1,Sum1 is Sum+F,fina(A1,B1,F1,Sum1). 問い3 13195 の素因数は 5, 7, 13, 29 である. 600851475143 の素因数のうち最大のものを求めよ. √まで求めればいいんだけどまあ小さい値で割り切れることはわかってるので特に気にしない。 soinn(1,N):-write(N),!. soinn(N,A):-0=:= N mod A,!,N1 is N/A,soinn(N1,A). soinn(N,A):-A1 is A+1,soinn(N,A1). 問い4 findallを使ってる時点で超手抜き。 末尾再帰で書くのが本当の正解。 kaibunn(C):- between(100,999,N), between(100,N,M), C is N*M, numrev(C,0,C1),C=:=C1. main4:-findall(C,kaibunn(C),List),mymax(List,0,Max),write(Max). 問い5 普遍的に解けるように書いてもよかったのだけど。 手抜きで解いた。 正しくは1~20までの素数のリストを求め、その素数aがa^n<=20となるnを求めてから計算する。 calc([],[],Ans):-!,write(Ans). calc([X|Rest],[Y|Rest1],Ans):-Ans1 is Ans*(X^Y),calc(Rest,Rest1,Ans1). main5:-Powers=[4,2,1,1, 1, 1,1 ,1], Base =[2,3,5,7,11,13,17,19], calc(Base,Powers,1). 問い6 うーんそのまま素直に実装するのが一番いいコードに思えるんだけど? なにか賢い解き方があるのかな? 数式一行になるとか? calc6(SumA,SumB,101):-!, Ans is SumB*SumB-SumA,write(Ans). calc6(SumA,SumB,N):- SumA1 is SumA+N*N, SumB1 is SumB+N, N1 is N+1, calc6(SumA1,SumB1,N1). 問い7 素数のリストを伸ばすだけの手抜き実装。 特徴遅い、、、 prime_check([X|Rest],N,[X|Re1],1):-N<X*X,!,append(Rest,[N],Re1). prime_check([X|Rest],N,[X|Rest],0):-0=:=N mod X,!. prime_check([X|Rest],N,[X|Result],Add):-prime_check(Rest,N,Result,Add). search7(_,N,10001):-!,N1 is N-1,write(N1). search7(PList,N,Count):- N1 is N+1, prime_check(PList,N,PList1,Add), Count1 is Count+Add, search7(PList1,N1,Count1). 問い8 Nに1000桁の数字を代入してResultで答えが返ってくる。 賢い方法ってあるのかしら? calc8(N,Ans,Ans):-N<10000,!. calc8(N,Max,Result):-N1 is N mod 10,N2 is (N//10) mod 10,N3 is (N//100) mod 10, N4 is (N//1000) mod 10,N5 is (N//10000) mod 10, Temp is N1*N2*N3*N4*N5,(Max<Temp->Max1 is Temp;Max1 is Max),NN is N//10,calc8(NN,Max1,Result). 問い9 1000=k((m^2+n^2)+2mn+(m^2-n^2)) を満たすk,m,nの組み合わせを見つける問題。 きちんと実装すると計算量は1000回以下になるが、まあ現状の500*24回でもそんなに悪くないと思う・ gcd(M,0,M):-!. gcd(M,N,Result):- N1 is M mod N, gcd(N,N1,Result). main9:- between(2,24,M), 0=:=500 mod M, between(1,500,R), 0=:=500 mod R, Sum is 500 //R, S is Sum // M, N is S-M, N<M, 0<N, gcd(M,N,Re), Re=:=1, 1=:=(M-N) mod 2, A is R*(M*M-N*N), B is R*2*M*N, C is R*(M*M+N*N), write([ans,A,B,C]).