コラム 人と星とともにある数学 数学

素数生成プログラム(エラトステネスのふるい)を実装|Pythonで数学を学ぼう! 第7回

今回はPythonでエラトステネスのふるいをプログラミングしてみましょう。

素数生成プログラム

「エラトステネスのふるい」は素数を見つける方法の1つです。

次がエラトステネスのふるいによって素数を生成するプログラムです。

>>> n =int(input("n以下の素数と個数を表示。n="))
>>> p = [i for i in range(n + 1)]

>>> for i in p[3:]:
>>>      if p[i] % 2 == 0:
>>>          p[i] = 0

>>> root_n = n ** 0.5
>>> for i in range(3, n):
>>>      if i > root_n:
>>>           break
>>>      if p[i] != 0:
>>>           for j in range(i, n + 1, 2):
>>>                if i * j >= n + 1 :
>>>                     break
>>>                p[i * j] = 0

>>> plist = sorted(list(set(p)))[2:]
>>> plistn = str(len(plist))+'個'

>>> print(plist)
>>> print(plistn)

実行するとnの値を尋ねられるので100と代入してみると、次のように表示されます。

n以下の素数と個数を表示。n=100
[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]
25個

100以下の素数が小さい順に表示されます。最後にその個数が25個と表示されます。

エラトステネスのふるい

エラトステネスのふるいのアルゴリズムをみていきます。

100以下の素数を探すことにします。

ステップ1

1番目の素数2に対して、2より大きな2の倍数4,6,8,10,12,…,100を消します。

ステップ2

1番目の素数2より次に大きな数を残った数の中から探します。それが2番目の素数3です。

残った数の中から3より大きな3の倍数である9,15,21,27,33,39,45,51,57,63,69,75,81,87,93,99を消します。

ステップ3

2番目の素数3より次に大きな数を残った数の中から探します。それが3番目の素数5です。

残った数の中から5より大きな5の倍数である25,35,55,65,85,95を消します。

ステップ4

3番目の素数5より次に大きな数を残った数の中から探します。それが4番目の素数7です。

残った数の中から7より大きな7の倍数である49,77,91を消します。

ステップ5

4番目の素数7より次に大きな数を残った数の中から探します。それが5番目の素数11です。

ここで、11は√100=10よりも大きくなったのでSTOPします。

ここで残った数が素数となります。

なぜ100の平方根(>0)よりも大きな素数が見つかったらSTOPするのか、わかりやすく小さな数36で説明してみます。

36をi×jに因数分解してみます。
i≦j
2×18
3×12
4×9
6×6

すると、最後の6が36の平方根だと分かります。iを6より大きな数にしてしまうと、それは既に計算されたjとなります。

ですから、36までの素数をエラトステネスのふるいで求める場合には、素数7が見つかった場合にSTOPしていいのです。

プログラムの解説

>>> p = [i for i in range(n + 1)]
により、
p[0]=0
p[1]=1
p[2]=2

p[100]=100
を生成します。

>>> for i in p[3:]:
>>>      if p[i] % 2 == 0:
>>>           p[i] = 0
p[3],p[4],…,p[100]の中で2の倍数のものを0に置き換えます。

これが先のステップ1に相当します。ステップ1での「消す」代わりに「0に置き換える」ことにします。

>>> root_n = n ** 0.5
>>> for i in range(3, n):
>>>      if i > root_n:
>>>           break
>>>       if p[i] != 0:
>>>           for j in range(i, n + 1, 2):
>>>                if i * j >= n + 1 :
>>>                     break
>>>                p[i * j] = 0

先に説明したようにi×jのiは√nより大きくなったらSTOPします。

それまでの間、0でないp[i]=iの倍数を「消す」代わりに「0に置き換える」ことを繰り返します。

>>> plist = sorted(list(set(p)))[2:]
これがこのプログラムの肝になるコードです。

ここまでに、
p[0]=0, p[1]=1, p[2]=2, p[3]=3, p[4]=0, p[5]=5, p[6]=0, p[7]=7, p[8]=0, p[9]=0, p[10]=0, p[11]=11,…, p[99]=0, p[100]=0
となっています。

そこで、set(p)とすることでp[i]を要素とする集合(set)を生成します。

このとき、前回説明したように重複する要素は自動的に削除され1つになります。

p[0]=0, p[4]=0, p[5]=5, p[6]=0, p[9]=0, p[10]=0, …, p[99]=0, p[100]=0
といった0が重複しているので、これらはまとめて1つの要素0となります。

はたして、
set(p)={11,29,2,61,7,0,…,3}
のように、集合の中身は大小バラバラの順に整理されます。

そこで、まずこれをlist()によりリスト化します。
list(set(p)) =[11,29,2,61,7,0,…,3]

その上で、sorted()することで大きさの順に並べ変えます。すると、
sorted(list(set(p)))=[0,1,2,3,5,7,11,…,97]
となります。

最後に、最初の2つの0(0番目)と1(1番目)が不必要なので、2番目の2から表示させます。
sorted(list(set(p)))[2:] =[2,3,5,7,11,…,97]

この最後の処理過程がわかるようにしたのが次のプログラムです。

>>> n =int(input("n以下の素数と個数を表示。n="))
>>> p = [i for i in range(n + 1)]

>>> for i in p[3:]:
>>>      if p[i] % 2 == 0:
>>>           p[i] = 0

>>> root_n = n ** 0.5
>>> for i in range(3, n):
>>>      if i > root_n:
>>>           break
>>>      if p[i] != 0:
>>>           for j in range(i, n + 1, 2):
>>>                if i * j >= n + 1 :
>>>                     break
>>>                p[i * j] = 0

>>> print(set(p))
>>> print(list(set(p)))
>>> print(sorted(list(set(p))))

>>> plist = sorted(list(set(p)))[2:]
>>> plistn = str(len(plist))+'個'

>>> print(plist)
>>> print(plistn)

実際にはnが100の場合には、はじめから大きさの順に並んでしまいます。

1000にしてみると、大きさがバラバラになり順に処理されていく様子がわかります。

記事の評価をお願いします!

  • この記事を書いた人
  • 最新記事

桜井進(さくらいすすむ)様

1968年山形県生まれ。 サイエンスナビゲーター®。株式会社sakurAi Science Factory 代表取締役CEO。 (略歴) 東京工業大学理学部数学科卒、同大学大学院院社会理工学研究科博士課程中退。 東京理科大学大学院非常勤講師。 理数教育研究所Rimse「算数・数学の自由研究」中央審査委員。 高校数学教科書「数学活用」(啓林館)著者。 公益財団法人 中央教育研究所 理事。 国土地理院研究評価委員会委員。 2000年にサイエンスナビゲーターを名乗り、数学の驚きと感動を伝える講演活動をスタート。東京工業大学世界文明センターフェローを経て現在に至る。 子どもから大人までを対象とした講演会は年間70回以上。 全国で反響を呼び、テレビ・新聞・雑誌など様々なメディアに出演。 著書に『感動する!数学』『わくわく数の世界の大冒険』『面白くて眠れなくなる数学』など50冊以上。 サイエンスナビゲーターは株式会社sakurAi Science Factoryの登録商標です。

-コラム, 人と星とともにある数学, 数学
-,

© 2021 株式会社インフォマティクス