PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 357 / 素数生成整数

30の約数について考えよう。

1,2,3,5,6,10,15,30

30の約数 d はそのすべてにおいて d+30/d の値が素数になる。

n のすべての約数 d について d+n/d が素数になるような 10^8 以下の正の整数 n の合計を求めよ。

Problem 357 - Project Euler


素数判定は PrimeQ[ ] で簡単にできますが,何の工夫もしないと滅茶苦茶時間がかかりそうなので,候補のしぼりこみからはじめます。

■半分のdについて調べればいい

f(x)=x+n/x とおきます。n=30 のとき f(1)=f(30), f(2)=f(15) などが成り立ち,一般に f(d)=f(n/d) です。Divisor[n] で約数を求めて,下半分について調べれば十分。

■n=p-1(pは素数)

f(1)=f(n)=n+1 は素数なので,n は素数から1引いた数です。

■nは squarefree

n=ab^2 (b≧2) のとき f(b)=ab^2+(ab^2)/b=ab(b+1) となり,これは素数ではありません。

■nは4の倍数ではない

n=p-1 は偶数です。4の倍数だとすると n=4m とおけます。
f(2)=2+4m/2=2(m+1)
これは素数ではありません。

以上をもとにコードを書きます。