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

プロジェクトオイラー問３ - (2014/02/12 (水) 08:41:07) のソース

*Problem 3 「最大の素因数」 †
13195 の素因数は 5, 7, 13, 29 である.
600851475143 の素因数のうち最大のものを求めよ.


解法
1ずつ増やしながらためし割りしていけば素数のときだけ割ることができます。
コードではたとえばｐで割れたらdiv述語でｐで割れるだけ割ってから次に進みます。
数字Nの素因数はN=p1^a1*p2^a^*,,,*pn^anですが、ｐiで割り切れば、piはｎから完全に消えます。
それ以外の素因数は消えません。
なので小さいほうから試しても素数以外で割ることがないということになります。


Prologは導出木と等価ですが、その分杓子定規な記述になります。
実際今回のコードを教科書的に記述してみましたがコードが膨らんでいますね。

Prologでは細部でコードを短くするのではなく、賢い導出木という全体設計でコードを短くするという話です。
複雑なものほどショートコードのし甲斐がある言語のようです。


 div(N,P,N):-N mod P>0,!.
 div(N,P,Result):-N1 is N // P,div(N1,P,Result).
 
 calc(1,_,Ans,Ans):-!.
 calc(N,P,_,Result):-
 	N<P*P,
 	!,
 	calc(1,N,N,Result).
 calc(N,P,_,Result):-
 	N mod P=:=0,
 	!,
 	div(N,P,N1),
  	P1 is P+1,
 	calc(N1,P1,P,Result).
 
 calc(N,P,Ans,Result):-
 	!,
  	P1 is P+1,
 	calc(N,P1,Ans,Result).
 
 main3:-
 	calc(600851475143,2,1,Ans),write(Ans).