* 素数判定を頑張って高速化してみる -エラトステネスの篩編-

まずはこの問題を見ていただきたい。

「6 桁以下の正の整数 n を入力し、n 以下の素数がいくつあるかを出力するプログラムを作成して下さい。ただし、素数とは 1 と自分自身でしか割り切れない正の整数のうち 1 をのぞいたものをいいます。例えば 10 以下の素数は、2, 3, 5, 7 です。」 引用:AOJ0009

なんてことはない、ただの素数判定です。

とはいえきちんとした素数判定のアルゴリズムをggってみるとどうやら『エラトステネスの篩』とやらがシンプルな方法らしい

(他にももっとあります)。

その他にもいろいろこちらで見させていただきました。

Pashango’s Blog:Pythonを使って高速判定してみる

peria.jp:エラトステネスの篩

ってことで私もPythonで実装してみた。


バージョンその1

  • 2 ~ nまでを順番にチェック
  • 気持ち早くするために、素数候補リストは奇数しか入れてない(これでチェックする量は半分で済む)
              #!/usr/bin/python
              
              def sieve(n):
                  nums = [i+1 for i in range(2, n, 2)]
                  ans = [2]
                  while len(nums) != 0:
                      for i in range(nums[0]*2, nums[-1]+1, nums[0]):
                          if i in nums: nums.remove(i)
                      ans.append(nums.pop(0))
                  return len(ans)
              
              print sieve(10000)
              

結果

python prime.py  0.84s user 0.01s system 98% cpu 0.861 total

5桁の素数であれば1秒以内に処理できます。

しかし6桁になると10分経っても結果が出ません。とてもじゃないけど使い物になりません。

毎素数で与えられた数字全てを走査しているので巨大な数に滅法弱いです。

ってことでちょっとずつ改良してみる。

バージョンその2

  • ある数 x で答え候補を篩にかける際、その前までの操作で x^2 以下の非素数は消されてるはず
  • なので今までは x ~ n でチェックしていたのを x^2 ~ n まで範囲を縮める

  • 今までなら5の場合 : 10 ~ n をチェック

  • 今回 : 25 ~ n をチェック

  • また、例えば120以下の素数をチェックする時、篩にかける数字が√120に達した時点で全ての素数を洗い出せているので

  • 今までなら5の場合 : 10 ~ n をチェック

  • 今回 : 25 ~ √n をチェック

              #!/usr/bin/python
              import math
              
              def sieve(n):
                  nums = [i+1 for i in range(2, n, 2)]
                  ans = [2]
                  while nums[0] <= math.sqrt(n): # ←ここが変わった
                      for i in range(nums[0]**2, nums[-1]+1, nums[0]): # ←ここも変わった
                          if i in nums: nums.remove(i)
                      ans.append(nums.pop(0))
                  ans += nums
                  return ans
              
              print sieve(10000)
              

結果

python prime.py  0.58s user 0.01s system 99% cpu 0.589 total

うん。気持ち早くなりましたね。

けど30000とか投げちゃうとまだまだ1,2秒かかる。

バージョン3

  • 偶数だけでなく、3と5の倍数も除去!
  • 理論上、チェックする数が半分以上減るので高速化が期待できる…はず
              #!/usr/bin/python
              import math
              
              def sieve(n):
                  nums = [i+1 for i in range(2, n, 2) if (i+1) % 3 != 0 and (i+1) % 5 !=0] # リスト内包表記で3,5の倍数をはじく
                  ans = [2,3,5] # 3,5は素数なので加えてしまう
                  while nums[0] <= math.sqrt(n):
                      for i in range(nums[0]**2, nums[-1]+1, nums[0]):
                          if i in nums: nums.remove(i)
                      ans.append(nums.pop(0))
                  ans += nums
                  return ans
              
              print sieve(10000)
              

結果

python prime.py  0.25s user 0.01s system 98% cpu 0.265 total

おおお!!

時間が先ほどの半分になりましたね。

もはや7とか11の倍数もはじけば早くなるのでは?と思ったけどそれだと素数判定 is 何となりかねないのでここらへんで。

実は素数判定にエラトステネスの篩が使われることは少なく(僕はあまり見たこと無い)、プログラムだとミラー・ラビンテストという方法でやるのが定石っぽい。

こっちもいつか記事にしたいなと思いつつ、先駆者の記事がすばらしいので多分書かないかも。

それでは。

追記

AOJでいろいろコードを見てたらとても美しいエラトステネスの篩の実装を見つけたので、そのコードを参考にして組み直しました。

そしたら激速…orz

以下コード。

              #!/usr/bin/python
              
              def sieve(n):
                  num = [True]*n
                  num[0] = num[1] = False
                  for i in xrange(2,int(n**0.5)+1):
                      if num[i]:
                          for j in xrange(i**2, n, i):
                              num[j] = False
                  return [i for i in xrange(2,n) if num[i]]
              
              print sieve(10000)
              

結果

python prime.py  0.03s user 0.01s system 90% cpu 0.038 total

0.01秒!!

素晴らしい。

ポイントとしては、

  • 最初にフラグリストを生成する。
  • i番目の数が素数ならTrue、素数じゃなければFalseというリストを最初に生成する。
  • 最後に、それを元にしてリストを生成する。

なるほどなぁ。そりゃ1と0を処理したほうが早いですもんね。

こういうことできるようになりたいですな。

以上でした。


※この記事は WordPress に投稿した記事を変換したものです。一部不自然な表示があるかも知れません。ご了承ください。また、記事タイトル先頭の * は WordPress から移行した記事である印です。

comments powered by Disqus