Pythonで素数判定のプログラムを作る方法を現役エンジニアが解説【初心者向け】
初心者向けにPythonで素数判定のプログラムを作る方法について現役エンジニアが解説しています。素数は1より大きい自然数、正の約数が1と自分自身のみである数のことです。素数判定のアルゴリズムの1つである試し割り法（エラトステネスのふるい）について解説します。
テックアカデミーマガジンは受講者数No.1のプログラミングスクール「テックアカデミー」が運営。初心者向けにプロが解説した記事を公開中。現役エンジニアの方はこちらをご覧ください。 ※ アンケートモニター提供元：GMOリサーチ株式会社 調査期間：2021年8月12日～8月16日 調査対象：2020年8月以降にプログラミングスクールを受講した18～80歳の男女1,000名 調査手法：インターネット調査
Pythonで素数判定のプログラムを作る方法を行う方法について解説します。
そもそもPythonについてよく分からないという方は、Pythonとは何なのか解説した記事を読むとさらに理解が深まります。
なお本記事は、TechAcademyのオンラインブートキャンプPython講座の内容をもとに紹介しています。
今回は、Pythonに関する内容だね！
どういう内容でしょうか？
Pythonで素数判定のプログラムを作る方法について詳しく説明していくね！
お願いします！
素数判定のための主なアルゴリズム
素数判定は、プログラミングの問題などでよく取り上げられるアルゴリズムです。
また現在多く使われている暗号アルゴリズムは、桁数が大きい合成数の素因数分解が困難であることをベースにしており、そこにも素数が関連しています。
Wikipediaによると、素数のアルゴリズムには以下のような種類があります。
- 試し割り法（エラトステネスのふるい）
- 最大公約数
- ウィルソンの定理
- Millerテスト
- APR判定法
- ECPP
- AKS素数判定法
- 確率的素数判定法
今回はこの中の「試し割り法（エラトステネスのふるい）」を取り上げます。
素数判定のプログラムを作る方法
素数判定だけでなく、一般的にプログラムを作成する場合は、最初に自然言語（日本語など）でその仕様を記述してから、プログラミングを開始するようにしましょう。
仕様漏れや矛盾などを実際にプログラムを作成する前に気づくことができます。テストを行う際も、その仕様に基づいて確認すれば良いため、プログラムの品質を担保できます。
今回は素数判定のプログラムを作成するので、まずは素数の定義から確認することにしましょう。
素数（そすう、英: prime number）とは、1 より大きい自然数で、正の約数が 1 と自分自身のみであるもののことである。正の約数の個数が 2 である自然数と言い換えることもできる。
続いて素数判定のアルゴリズムである、エラトステネスのふるいについて確認します。
1.探索リストに2からxまでの整数を昇順で入れる。
2.探索リストの先頭の数を素数リストに移動し、その倍数を探索リストから篩い落とす。
3.上記の篩い落とし操作を探索リストの先頭値がxの平方根に達するまで行う。
4.探索リストに残った数を素数リストに移動して処理終了。
仕様確認が終わりました。後はこれらの仕様をもとに、プログラミングを行っていきます。
実際に書いてみよう
今回のサンプルプログラムでは、エラトステネスのふるいを応用して素数判定を行います。
入力した数が素数か否か判定を行うため、探索リストを使わず、入力した数を割っていくことで素数かどうかを判定しています。
# 画面からの入力や終了を行う
import sys
# 平方根の計算や切り上げを行う
import math
# 画面からの入力を受け取る
tmp = input("整数を入力してください")
# 数値チェック
try:
val = int(tmp)
except Exception as e:
print("数値以外が入力されました")
# プログラムを終了する
sys.exit()
# 1より大きいかチェック
if val <= 1:
print("1以下が入力されました")
sys.exit()
# 素数ならTrue
flg = True
# 検索する最大値
max_search = math.ceil(math.sqrt(val))
if val <= 3:
# 3以下なら素数
pass
else:
for i in range(2, max_search):
if val % i == 0:
flg = False
break
# メッセージを表示
if flg:
print("素数")
else:
print("素数ではない")
実行結果は以下のようになります。
整数を入力してください 97 素数
監修してくれたメンター
| 太田和樹（おおたかずき）
ITベンチャー企業のPM兼エンジニア 普段は主に、Web系アプリケーション開発のプロジェクトマネージャーとプログラミング講師を行っている。守備範囲はフロントエンド、モバイル、サーバサイド、データサイエンティストと幅広い。その幅広い知見を生かして、複数の領域を組み合わせた新しい提案をするのが得意。 開発実績：画像認識技術を活用した駐車場混雑状況把握（実証実験）、音声認識を活用したヘルプデスク支援システム、Pepperを遠隔操作するアプリの開発、大規模基幹系システムの開発・導入マネジメント。 地方在住。仕事のほとんどをリモートオフィスで行う。通勤で消耗する代わりに趣味のDIYや家庭菜園、家族との時間を楽しんでいる。 |
内容分かりやすくて良かったです！
ゆかりちゃんも分からないことがあったら質問してね！
分かりました。ありがとうございます！
TechAcademyでは、初心者でもPythonを使った人工知能（AI）や機械学習の基礎を習得できるオンラインブートキャンプPython講座を開催しています。
挫折しない学習方法を知れる説明動画や、現役エンジニアとのビデオ通話とチャットサポート、学習用カリキュラムを体験できる無料体験も実施しているので、ぜひ参加してみてください。
