PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 234 / 半分割可能数

整数n(≥4)に対して最大の素数(≤√n)を n の下位素数平方根(lower prime square root)とし,lps(n)であらわす。同様に最小の素数(≥√n)を n の上位素数平方根(upper prime square root)とし,ups(n)であらわす。

lps(4) = 2 = ups(4), lps(1000) = 31, ups(1000) = 37 である。

lps(n) と ups(n) のどちらかが n を割り切るが,両方ではないとき整数n(≥4)を半分割可能(semidivisible)と呼ぶ。

15 を超えない半分割可能な数は8, 10, 12で,それらの合計は 30 である。15 は lps(15) = 3 と ups(15) = 5の両方の倍数なので半分割可能でない。さらに例を挙げると,1000 までの半分割可能な整数 92 個の合計は 34825 である。

999966663333 を超えない半分割可能な数全ての合計を求めよ。

Problem 234 - Project Euler


lps(n)=ups(n) だと「両方ではない」の条件をみたさないので,n は平方数ではありません。 p< \sqrt{n}< q をみたす連続する素数 p, q が存在します。平方すると

 p^2< n< q^2

この範囲で
(p の倍数の和) + (q の倍数の和) - (pq の倍数の和)*2
を計算して足しあわせます。

ただし,最後の素数 p についてだけ,n が 999966663333 を超えるかどうかのチェックが必要です。下のコード中で sum1=0 なのですが,一応調べました。


Sum を2次関数であらわに書くと若干早くなります。1秒→0.8秒の微妙な変化ですが。