PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 187 / 半素数

合成数とは2つ以上の素因数を含む整数のことである。たとえば 15=3×5, 9=3×3, 12=2×2×3 は合成数である。

30以下にはちょうど2つの素因数を含む合成数(異なる素因数でなくてもよい)が10個存在する。4, 6, 9, 10, 14, 15, 21, 22, 25, 26である。

自然数 n < 10^8 について,ちょうど2つの素因数を含む合成数(異なる素因数でなくてもよい)はいくつあるか。

Problem 187 - Project Euler

brute force

Mathematica がおあつらえ向きの関数 PrimeOmega[n] を用意してくれていました。n における重複を数えた素因数の数 Ω(n) を返します。ちなみに,異なる素因数の数 ν(n) を与える PrimeNu[n] も用意されています。

PrimeOmega[k] = 2 となる k を数えるだけで解けますが,6分以上かかってしまいます。


公式を使おう

semiprime でググると Wolfram Mathworld がヒットし,そこには個数を与える公式が載っています。

Semiprime -- from Wolfram MathWorld

 \pi^{(2)}(x)=\displaystyle\sum_{k=1}^{\pi(\sqrt{x})} \left\{\pi\left(\frac{x}{p_k}\right)-k+1\right\}

左辺は x 以下の半素数の個数,π(x)は x 以下の素数の個数,p_k は k 番目の素数です。すべて Mathematica に組み込まれているので,ありがたく利用させていただきます。結果は0.03秒。さすがに速い。