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

プロジェクトオイラー問２７ - (2014/02/14 (金) 05:40:33) のソース

Problem 27 「二次式素数」 †
オイラーは以下の二次式を考案している:

n＾2 + n + 41.
この式は, n を0から39までの連続する整数としたときに40個の素数を生成する. しかし, n = 40 のとき 40＾2 + 40 + 41 = 40(40 + 1) + 41 となり41で割り切れる. また, n = 41 のときは 41＾2 + 41 + 41 であり明らかに41で割り切れる.

計算機を用いて, 二次式 n＾2 - 79n + 1601 という式が発見できた. これは n = 0 から 79 の連続する整数で80個の素数を生成する. 係数の積は, -79 × 1601 で -126479である.

さて, |a| < 1000, |b| < 1000 として以下の二次式を考える (ここで |a| は絶対値): 例えば |11| = 11 |-4| = 4である.

n＾2 + an + b
n = 0 から始めて連続する整数で素数を生成したときに最長の長さとなる上の二次式の, 係数 a, b の積を答えよ.


解法
ｎ＝0の時ｂが素数でないと条件を満たさない。
n=3の時aは奇数でないと条件を満たさない。
-ｂよりaは大きくないといけない。
後はこの条件で全部検討するだけ。
全部の場合のリストを選んでソートしているので多少遅い。
たぶんもっとかしこ方法はあると思う。


 not_prime(P):-P<2,!.
 not_prime(2):-!,fail.
 not_prime(P):-
 	between(2,P,Div),
 	(Div^2>P->!,fail;true),
 	P mod Div=:=0,
 	!.
 is_prime(P):-!,not(not_prime(P)).
 
 not_prime2(P,_):-P<2,!.
 not_prime2(2,_):-!,fail.
 not_prime2(P,Ps):-
 	member(Div,Ps),
 	(Div^2>P->!,fail;true),
 	P mod Div=:=0,
 	!.
 is_prime2(P,Ps):-!,not(not_prime2(P,Ps)).
 
 
 
 search(Ps,A,B,Len,Len):-
 	F is Len*Len+Len*A+B,
 	not_prime2(F,Ps),
 	!.
 search(Ps,A,B,Len,Result):-
 	!,
 	Len1 is Len+1,
 	search(Ps,A,B,Len1,Result).
 
 calc([Len,A1,B1],Ps):-
 	between(1,499,B),
 	B1 is B*2+1,
  	is_prime2(B1,Ps),
 	BM is -B1,
 	between(BM,999,A1),
 	A1 mod 2=\=0,
 	search(Ps,A1,B1,0,Len).
 prime_list(P):-
 	between(2,2000,P),
  	is_prime(P).
 
 
 main27:-
 	findall(P,prime_list(P),Ps),
 	findall(Set,calc(Set,Ps),Sets),
 	sort(Sets,Sets1),
 	write(Sets1).