Pythonで素数を調べ上げる
1.はじめに
ざっくり言うと、入力した値までの素数を出力するプログラムを書きたいというのが今回の目的です。片っ端から入力した値未満の数で割って調べていくこともできますが、パソコンの処理能力を考え、できるだけ人間がやる操作に近い、効率的な方法を考えながらコードを書きました。
2.具体的に
初めにリストに2を入れておきます。次に3は2では割り切れないので、リストに追加します。次に4が2と3で割り切れるかを調べます。4は偶数なので、無視します。
このように、入力した数以下のある数について、それ未満の素数からなるリストを参照し、リスト内のどの数でも割り切れなければ、新たな素数としてリストに加えます。この操作を、対象の数の値を増やしながら調べていきます。
3.もっと具体的に
入力値を受け取ります。
n = int(input())
リストを作ります。
prime_list = [2]
入力値以下のある数の初期値を2に設定します。
#iは「ある数」のこと
i = 2
次に以下を記述します。これについては後述します。
count = 0
入力した数以下のある数について、それ未満の素数からなるリストを参照し、リスト内のどの数でも割り切れなければ、新たな素数としてリストに加えます。この操作を、対象の数の値を増やしながら調べていきます。（使いまわし）
#入力値以下のある数について
while i <= n:
#素数リストに入ってる数itemを順番に取り出し、操作する
for item in prime_list:
#itemがiで割り切れるならば
if i % item == 0:
#countに1を追加する
count += 1
#そうでなければ
else:
#無視する
count += 0
#countが0のままだったら
if count == 0:
#iを新たな素数としてリストに追加する
prime_list.append(i)
#iに1を足して次の操作に進む
i += 1
#そうでなければ
else:
#countを0にリセットする
count = 0
#iに1を追加して次の操作に進む
i += 1
素数リストが出来上がったので、あとは好きに使って下さい。
#リスト内の素数を順に出力する
for item in prime_list:
print(item)
4.反省と課題
今回1番苦労したのは、やはりcountの概念の導入です。これをしないと、素数リスト内にある素数で割れない数をすべて追加するので、大変なことになります。例えば、4は2で割り切れるので無視しますが、3では割り切れないので、4をリストに追加してしまいます。5の場合であれば、2と3と(既に追加した)4で割り切れないので、リストに5を3つ追加します。カオスです。
割り切れた数にはcountしていき、最終的にcountが0を貫いた数は、リスト内のどの素数でも割れない数、つまり新たな素数です。なんとか思いついて良かったです。
しかし課題もあります。私たちはある数の約数を調べるとき、その数の正の平方根に満たない数しか調べません。それをこれにも適用すれば、もっと速く計算できると思ったのですが、私の知識不足で、当分の間は解決できそうにありません。有識者は私に教えて下さると助かります。他にもこの記事で何かおかしい点等ありましたら気軽にご指摘下されば幸いです。
Discussion