Dirichlet's Theorem on Arithmetic Progressions 解説

アルゴリズムの概略

素数関係の問題です。 素数を求めたり使ったりする問題は多く，この問題はそのうち最も簡単な部類でしょう。 ICPCでは，素数判定を含めて，数論（整数論）関連の数学的な問題もよく出てきます。

この問題は素数表を作れば後は簡単です。 問題で与えられているように，この問題では 1,000,000 以上の素数が出てきません。 素数表が出来れば，後は a に d を足していって，値が素数であればカウントし，n番目の素数を出力するだけです。 なので，ある程度高速に素数表が作れるアルゴリズムが必要です。

さて，高速に素数表を作るアルゴリズムはいくつかありますが， あらかじめ必要な素数の範囲が分かっていて，与えられた値が素数であるかないかを判定したい場合（つまり素数表のルックアップテーブル (loopup table) を作りたい場合）は 「エラトステネスの篩」が使えます。

詳細は上記リンク先のWikipediaのページが詳しいのでここでは述べません。 平方根まで調べればよい理由については書かれていないようなので述べておきましょう。 もし p が素数でなければ a と b の積に分割できます。 例えば 27 = 3×9 などです。 で，p = 27 が a = 3 < sqrt(p) で割れれば，対応する b = 9 > sqrt(p) が存在することが分かります。 逆に a < sqrt(p) が存在しなければ sqrt(p) を超える割り切れる値は存在しません。 ですので，a = b = sqrt(p) までチェックすれば十分なのです。 従って，sqrtを使うのが面倒であれば MAX/2 などで代用しても構いません（遅くはなりますが）。

この問題のように素数表が欲しい場合はエラトステネスの篩そのままでOKですが， 素数の配列が欲しいような場合があれば「Sum of Different Primes」の解答例で使っているような方法が良いでしょう。

アルゴリズムの計算量

このアルゴリズムは素数表を求める部分と，それをチェックして問題を解く部分に分かれます （ただし，このような問題ではこれ以上高速なアルゴリズムはそうそう考えられるものではないので， 通常は有名な高速アルゴリズムが適用できれば計算量はあまり考える必要はありません）。

まず，素数表を求める部分の計算量を求めてみましょう。。 今回は n = 1,000,000 なので外側のループは sqrt(n) = 1,000 まで調べることになります。 ループ変数を i とすると，i = 2 の場合は内側のループは n / 2 = 500,000 回まわります。 i = 1000 の場合は n / 1000 = 1000 回まわります。 ですので，正確な計算量は (n/2) + (n/3) + … + (n/999) + (n/1000) になります。 100,000回以上まわるような大きなループは少ないので，概算は 1,000,000 + 10,000 × 1000 くらいでしょうか。 そうすると 11,000,000 = 11M 回くらいで，1秒以内には計算できそうです*1。

素数表を使って問題を解く部分は，素数のばらつき度に依存するので，ある程度でも正確な計算量を求めることはかなり困難です。 まぁ，素数表よりも速い判定法なぞなかなか無いでしょうから，計算量は求めなくても安心して解き始められますが。

アルゴリズムの実装

コメントするほどの注意点はありません。 強いて挙げれば，sqrtを取った際に誤差で切り捨てられるのが怖い（sqrt(10000) = 99.99999… となって 99 になって欲しくない）ので sqrt(MAX) ではなく sqrt(MAX) + 1 あたりを上限判定に使った方が安心できます。 それと 1 は（定義により）素数ではありません。

補足1: 実際に正確な値の方を計算してみると 6,485,017 回だそうです。 ちなみに i = 2 の場合は別のループで全て 0 にして，奇数のみを対象にして i = 3 から i を 2 ずつ増やしていくと， 全体の計算量が半分くらいになるようです。

$Id: index.shtml 1335 2007-03-01 09:06:39Z SYSTEM $