【モジュールなし】Pythonで素数を列挙するリストを簡単に生成する方法

モジュールやライブラリを使わず、Pythonで素数のリストを出力するコードを書いてみました。

素数とは

1とその数以外では割り切れない正の整数のこと。ただし1は除く(素数の始まりは2から)
理論的に素数は無限に存在し、大きい素数になるほどスーパーコンピュータで処理しないと計算できなくなります。

目次

素数判定しリストを出力するPythonコード全文

今回は素数の定義に基づいて、ある整数Nを手前の数N-1まで総当たりで割り算して、割り切れることがなければ素数という判定をさせています(これを試し割り法と言います)

コード全文は以下の通り。
Pythonはインデント(字下げ)で処理が変わるのでコピペの際はご注意ください。

def prime(N):
  primes = []
  for i in range(2, N + 1):
    primes.append(i)
    for p in range(2, i):
      if i % p == 0:
        primes.remove(i)
        break
  return primes

print(prime(N))

最後のprint関数のNに数字を入れれば、その数までの素数リストを出力してくれます。
仮にNに200を入力して実行すると、出力結果は以下のようになります。

[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]

各コードの解説

まず素数リストを計算する関数primeをdef関数で定義。
そのあとprimes変数に空っぽのリストを代入します。

def prime(N):
primes = []

素数の最初の数である2からNまでの整数を変数iに繰り返し代入するfor関数を定義。
このiに入った数字を素数かどうか判定していきます。
またrange関数で最後をN+1としているのは、range関数は最後の数の1つ手前の数字までしか代入しないというルールだからです。(例:N+1=201で、200まで計算される)

for i in range(2, N + 1):

いったん変数iをprimesリストにappend(追加)

primes.append(i)

再びfor関数で2からiまでの数字を繰り返しpに代入する処理。

for p in range(2, i):

iがpで割り切れるか(商の余りが0か)をif関数で判定。
割り切れたらiは素数じゃなかったことになるので、primeリストからiをremove(削除)
breakで処理を終了して、for i in range〜の処理に戻り、iに次の整数が代入されてまた素数判定を繰り返します。

if i % p == 0:
primes.remove(i)
break

最後にprime関数にprimes変数をreturnで返して終了。
確認のため、prime関数をprintで出力させています。実際に素数リスト(prime関数)だけ欲しい場合は必要ありません。

return primes
print(prime(N))

以上、少しでも参考になれば幸いです。

よかったらシェアしてね!

この記事を書いた人

37歳。名古屋工業大学大学院卒業
某中堅モーターメーカーに就職
AIの自主勉強をはじめた品質管理マン
↓リンクで『AIと品質管理』トップへ

コメント

コメントする

CAPTCHA


目次
閉じる