「プロジェクトオイラー問１２３」の編集履歴（バックアップ）一覧はこちら

「プロジェクトオイラー問１２３」(2014/03/09 (日) 00:43:59) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20123

*Problem 123 「素数の自乗で割った余り」 †
pn を n 番目の素数とする. (p1 = 2, p2 = 3, ...) r を (pn - 1)n + (pn + 1)n を pn^2 で割った余りとする.

例えば, n = 3 のとき, p3 = 5 であり, 4^3 + 6^3 = 280 ≡ 5 mod 25.

余り r が 10^9 より大きくなる n の最小値は 7037 である.

余り r が 10^10 より大きくなる最初の n を求めよ.

解法
愚直に小さいほうから試す以外思いつきません。
何か賢い解法でもあるものでしょうか？

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20123

*Problem 123 「素数の自乗で割った余り」 †
pn を n 番目の素数とする. (p1 = 2, p2 = 3, ...) r を (pn - 1)n + (pn + 1)n を pn^2 で割った余りとする.

例えば, n = 3 のとき, p3 = 5 であり, 4^3 + 6^3 = 280 ≡ 5 mod 25.

余り r が 10^9 より大きくなる n の最小値は 7037 である.

余り r が 10^10 より大きくなる最初の n を求めよ.

解法
愚直に小さいほうから試す以外思いつきません。
何か賢い解法でもあるものでしょうか？
 

 not_prime(N):-
 	between(2,N,D),
 	(D*D>N->!,fail;true),
 	N mod D=:=0,
 	!.
 is_prime(N):-not(not_prime(N)).
 
 
 search(N,No):-
 	is_prime(N),
 	!,
 	No1 is No+1,
 	N1 is N+1,
 	(No1 mod 2=:=0->M is 2;M is 2*N*No1),
 	(M>10^10->!,write(No1);search(N1,No1)).
 search(N,No):-
 	!,
	N1 is N+1,
 	search(N1,No).
 main123:-
 	search(2,0).