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

今回も強引にpythonのリストを使います。
「エラトステネスの篩(ふるい)」で素数を求めてみます。

まず、偶数で素数は2しかありませんので、引数で指定した数を上限とした3からの奇数のみリストにします。

takk@deb83:~$ cat -n test.py
takk@deb83:~$ 

実行してみます。

takk@deb83:~$ python test.py 8
[3, 5, 7]
takk@deb83:~$ python test.py 9
[3, 5, 7, 9]
takk@deb83:~$ python test.py 10
[3, 5, 7, 9]
takk@deb83:~$ python test.py 11
[3, 5, 7, 9, 11]
takk@deb83:~$ 

次にrestの先頭の数の倍数を、restから取り除くためのふるいリストsieveを作ります。

     1	import sys
     2	
     3	maxnum = int(sys.argv[1])
     4	rest=[x*2+1 for x in range(1,(maxnum+1)/2)]
     5	
     6	a=rest.pop(0)
     7	sieve=[x*a for x in range(1,maxnum/a+1)]
     8	
     9	print rest
    10	print sieve

takk@deb83:~$ python test.py 15
[5, 7, 9, 11, 13, 15]
[3, 6, 9, 12, 15]
takk@deb83:~$ 

そして、restからsieveを引くと(set(rest) – set(sieve))
[5, 7, 11, 13]が求まるということです。

ソースはこうなりました。

takk@deb83:~$ cat -n erastothenes.py
     1	import sys
     2	
     3	maxnum = int(sys.argv[1])
     4	rest=[x*2+1 for x in range(1,(maxnum+1)/2)]
     5	
     6	prime=[2]
     7	
     8	while 1:
     9		if len(rest)==0:
    10			break
    11	
    12		a=sorted(rest).pop(0)
    13		sieve=[x*a for x in range(1,maxnum/a+1)]
    14		rest = set(rest) - set(sieve)
    15		prime.append(a)
    16	
    17	print prime

100までの素数を求めます。

takk@deb83:~$ python eratosthenes.py 100 | fold -s40
[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]
takk@deb83:~$