Problem 27 「二次式素数」 †
オイラーは以下の二次式を考案している:
n2 + n + 41.
この式は, n を0から39までの連続する整数としたときに40個の素数を生成する. しかし, n = 40 のとき 402 + 40 + 41 = 40(40 + 1) + 41 となり41で割り切れる. また, n = 41 のときは 412 + 41 + 41 であり明らかに41で割り切れる.
計算機を用いて, 二次式 n2 - 79n + 1601 という式が発見できた. これは n = 0 から 79 の連続する整数で80個の素数を生成する. 係数の積は, -79 × 1601 で -126479である.
さて, |a| < 1000, |b| < 1000 として以下の二次式を考える (ここで |a| は絶対値): 例えば |11| = 11 |-4| = 4である.
n2 + an + b
n = 0 から始めて連続する整数で素数を生成したときに最長の長さとなる上の二次式の, 係数 a, b の積を答えよ.
解法
まずn=0で成り立つことから考えてｂは0以上の素数です。
次に式から考えてグラフは下に凸です。
ｂを決めた後aを決めて
n=1のとき２以上でないならaはそれ以下の値をとりません。
n=1のとき２以上でないならaはそれ以下の値をとりません。
これによって探索範囲はそれなりに狭まりました。
ここまで狭まればまあコードを書こうという気にもなります。
not_prime(P):-
between(2,P,Div),
(Div^2>P->!,fail;true),
P mod Div=:=0,
!.
is_prime(P):-!,not(not_prime(P)).
stop(_,A):-A>=1000,!.
stop(B,A):-A<1-B,!.
stopB(B):-B>=1000,!.
f(N,B,A,Result):-Result is N^2+A*N+B,!.
roopN(N,B,A,[N1,Ans]):-
f(N,B,A,Y),
not_prime(Y),
Ans is B*A,
N1 is N+1,
!.
roopN(N,B,A,Result):-
!,
N1 is N+1,
roopN(N1,B,A,Result).
roopA(B,A,_):-
stop(B,A),!,fail.
roopA(B,A,Result):-
roopN(0,B,A,Result).
roopA(B,A,Result):-
!,
A1 is A-1,
roopA(B,A1,Result).
roopB(B,Ans,Ans):-
stopB(B),
!.
roopB(B,[Len,_],Result):-
is_prime(B),
roopA(B,999,[Len1,Ans1]),
Len<Len1,
!,
B1 is B+1,
roopB(B1,[Len1,Ans1],Result).
roopB(B,Ans,Result):-
!,
B1 is B+1,
roopB(B1,Ans,Result).
main27:-
roopB(2,[0,0],Ans),
write(Ans).
0 件のコメント:
コメントを投稿