整数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 を超えない半分割可能な数全ての合計を求めよ。
lps(n)=ups(n) だと「両方ではない」の条件をみたさないので,n は平方数ではありません。 をみたす連続する素数 p, q が存在します。平方すると
この範囲で
(p の倍数の和) + (q の倍数の和) - (pq の倍数の和)*2
を計算して足しあわせます。
ただし,最後の素数 p についてだけ,n が 999966663333 を超えるかどうかのチェックが必要です。下のコード中で sum1=0 なのですが,一応調べました。
Sum を2次関数であらわに書くと若干早くなります。1秒→0.8秒の微妙な変化ですが。