エラトステネスの篩

Pythonで素数を求めるプログラムを書いてみました。

Basic、Fortran的なコーディングはこんな感じです。

for i in range(1,101,1):                                    # i 　1から100まで調べる
    k = 0                                                   # k    素数カウント用
    for j in range(1,101,1):                                # j 　1から100で割ってみる
        if i >= j:                                          # iがjより大きい時だけ
             if (i % j) == 0:k +=1                          # k  で0で割れた数を数える
    if k==2:print(i)                                        # k　自分と１だけで割れた数字をプリント

Pythonの特徴を活かすとこんなところでしょう。

for i in range(3, 1001, 2):									# 3から偶数だけ選択
    sosu = True
    for n in range(2, i):
        if i % n == 0:
            sosu = False
            break
           													 # 割り切れる素数ではない
        array.append(i)
print(array)

Pythonで素数を篩にかけているイメージが分かりやすいコーディングはこんな感じです。

for i in range(1, 101, 1):			    # 1から100までの連続する整数値を画面に表示

    if   i == 1 :                       # １は素数ではない
        continue

    if  (i != 2) and (i % 2) == 0 :     # 2を除いた2の倍数は素数ではない
        continue
        
    if  (i != 3) and (i % 3) == 0 :     # 3を除いた3の倍数は素数ではない
        continue
            
    if  (i != 5) and (i % 5) == 0 :     # 5を除いた5の倍数は素数ではない
        continue           

    if (i != 7) and (i % 7) ==0 :       # 7を除いた7の倍数は素数ではない
        continue

    print(i)                            # 篩い落とされたものが素数

プログラムの説明は割愛します。

素数
1と自分自身以外では割り切れない自然数。2、3、5、7、11、13、17、19……と続き、無限個存在することが、古代ギリシャでユークリッドによって示されていた。「3と5」、「5と7」、「11と13」のように、偶数の両隣の組になっている素数を双子(ふたご)素数という。双子素数は無限個あると予想されているが、未解決である。知られている最大の双子素数は2003663613×(2の195000乗)±1(2007年9月現在)。また、4以上の偶数は2つの素数の和として書けるという予想(ゴールドバッハの予想: Goldbach conjecture)も未解決。4=2+2、6=3+3、8=3+5など。大きな素数は公開鍵暗号に利用されている。コンピューターを使い大きな素数を発見する研究が行われており、2006年9月に発見された2(2の32582657乗)-1が、現在具体的に知られている最大の素数。その桁数は約981万桁(けた)。このように、(2のn乗)-1の形の素数はメルセンヌ(Mersenne)素数と呼ばれ、07年9月末現在、素数になるnが計44個知られている。素数の分布はリーマンのゼータ関数(リーマン予想)と関係している。ある自然数が素数であるかどうかを判定することは実用上重要であるが、02年にアグラワル(M.Agrawal)、カヤル(N.Kayal)、サクセナ(N.Saxena)の3人のインド人研究者によって、多項式時間で判定できるという驚くべき結果が得られた。

知恵蔵
PAGE TOP