素数をエラトステネスのふるいで求める

NHKのポアンカレ予想とリーマン予想のYoutubeを見てなんとなくやってみたくなった。なんとかの篩(ふるい)っていうのは耳にしたことがあったので、まずはそれをやってる。

以下のソースコードをeratosthenes.pyという名前で保存して、

python eratosthenes.py <max number>

で実行。

#!/usr/bin/python
# -*- coding:utf-8 -*-

import sys
import math

def multiple_del(li, prime):
  mn = prime
  for i in li:
    if i > mn:
      mn += prime
    if i == mn:
      li.remove(mn)
      mn += prime

def print_format(l, nsep, digit, ssep = ""):
  f = "%" + str(digit) + "d"
  for i in range(len(l)):
    print f % (l[i]),
    print ssep,
    if (i+1) % nsep == 0:
      print ""

def get_digit(n):
  return int(math.log10(n) + 1)

if __name__ == '__main__':
  argv = sys.argv
  argvc = len(argv)
  if argvc != 2:
    print "Please enter max number"
    print "python eratosthenes.py <max number>"
    exit()
  else:
    nmax = int(argv[1])
    li = range(2, nmax+1)
    lp = []
    while len(li) != 0:
      pn = li[0]
      lp.append(pn)
      multiple_del(li, pn)
    print "prime number (<",
    print nmax,
    print ")"
    print_format(lp, 10, get_digit(nmax))

1000までの出力結果

[guest@localhost eratosthenes]$ python eratosthenese.py 1000
prime number (< 1000 )
   2     3     5     7    11    13    17    19    23    29  
  31    37    41    43    47    53    59    61    67    71  
  73    79    83    89    97   101   103   107   109   113  
 127   131   137   139   149   151   157   163   167   173  
 179   181   191   193   197   199   211   223   227   229  
 233   239   241   251   257   263   269   271   277   281  
 283   293   307   311   313   317   331   337   347   349  
 353   359   367   373   379   383   389   397   401   409  
 419   421   431   433   439   443   449   457   461   463  
 467   479   487   491   499   503   509   521   523   541  
 547   557   563   569   571   577   587   593   599   601  
 607   613   617   619   631   641   643   647   653   659  
 661   673   677   683   691   701   709   719   727   733  
 739   743   751   757   761   769   773   787   797   809  
 811   821   823   827   829   839   853   857   859   863  
 877   881   883   887   907   911   919   929   937   941  
 947   953   967   971   977   983   991   997