PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 268 / 少なくとも4つの異なる100未満の素数を因数に持つ数

少なくとも 4 つの異なる 100 未満の素数で割り切れる 1000 未満の正の整数は 23 ある。

少なくとも 4 つの異なる 100 未満の素数で割り切れる 10^16 未満の正の整数はいくつあるか答えよ。

Problem 268 - Project Euler


まずは単純な場合を考えました。たとえば「2, 3, 5 のうち少なくとも2つで割り切れるような n 以下の自然数の個数を求めよ」だったら? 素数を1個しか含まない数を数えて全体から引くのが自然ですが,この解法は今考えている問題には向かないので普通に数えます。

f(x)=[n/x]([ ]はガウス記号)とおいて,ベン図を考えると

 f(2\cdot 3)+f(3\cdot 5)+f(5\cdot 2)-2f(2\cdot 3\cdot 5)

これを一般化します。

上式の最後の項の係数が1ではないのが,この問題一番の難所でした。k(≧4)個の数を考えるとき,ここには
C(k,4) - C(k,5) + C(k,6) + ... + (-1)^(k-4)C(k,k)
が来ます。このままでも計算できますが,C(k-1,3) とまとめられることに気づくと速いです。

また,100未満の素数は25個ありますが,これら全部を相手にする必要はありません。素数を14個以上かけると 10^16 を超えてしまうので,最大13個の素数で割り切れる数を考えれば十分です。

あと,細かいことですが「割り算してガウスをとる」よりも「商を求める」の方が速いようです。これだけで時間が約半分になりました。