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

Problem 3 「最大の素因数」 †

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


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


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