Pythonで素数判定のプログラムを作る方法を現役エンジニアが解説【初心者向け】

初心者向けにPythonで素数判定のプログラムを作る方法について現役エンジニアが解説しています。素数は1より大きい自然数、正の約数が1と自分自身のみである数のことです。素数判定のアルゴリズムの1つである試し割り法(エラトステネスのふるい)について解説します。

TechAcademyマガジンはオンラインのプログラミングスクールTechAcademy [テックアカデミー]が運営する教育×テクノロジーのWebメディアです。初心者でもすぐ勉強できる記事が2,000以上あります。

Pythonで素数判定のプログラムを作る方法を行う方法について解説します。

Pythonについてそもそもよく分からないという方は、Pythonとは何なのか解説した記事をまずご覧ください。

 

なお本記事は、TechAcademyのPythonオンライン講座の内容をもとにしています。

 

田島悠介

今回は、Pythonに関する内容だね!

大石ゆかり

どういう内容でしょうか?

田島悠介

Pythonで素数判定のプログラムを作る方法について詳しく説明していくね!

大石ゆかり

お願いします!

 

素数判定のための主なアルゴリズム

素数判定は、プログラミングの問題などでよく取り上げられるアルゴリズムです。

また現在多く使われている暗号アルゴリズムは、桁数が大きい合成数の素因数分解が困難であることをベースにしており、そこにも素数が関連しています。

Wikipediaによると、素数のアルゴリズムには以下のような種類があります。

  • 試し割り法(エラトステネスのふるい)
  • 最大公約数
  • ウィルソンの定理
  • Millerテスト
  • APR判定法
  • ECPP
  • AKS素数判定法
  • 確率的素数判定法

今回はこの中の「試し割り法(エラトステネスのふるい)」を取り上げます。

 

素数判定のプログラムを作る方法

素数判定だけでなく、一般的にプログラムを作成する場合は、最初に自然言語(日本語など)でその仕様を記述してから、プログラミングを開始するようにしましょう。

仕様漏れや矛盾などを実際にプログラムを作成する前に気づくことができます。テストを行う際も、その仕様に基づいて確認すれば良いため、プログラムの品質を担保できます。

今回は素数判定のプログラムを作成するので、まずは素数の定義から確認することにしましょう。

素数(そすう、英: prime number)とは、1 より大きい自然数で、正の約数が 1 と自分自身のみであるもののことである。正の約数の個数が 2 である自然数と言い換えることもできる。

Wikipedia

続いて素数判定のアルゴリズムである、エラトステネスのふるいについて確認します。

1.探索リストに2からxまでの整数を昇順で入れる。
2.探索リストの先頭の数を素数リストに移動し、その倍数を探索リストから篩い落とす。
3.上記の篩い落とし操作を探索リストの先頭値がxの平方根に達するまで行う。
4.探索リストに残った数を素数リストに移動して処理終了。

Wikipedia

仕様確認が終わりました。後はこれらの仕様をもとに、プログラミングを行っていきます。

 

[PR] Pythonで挫折しない学習方法を動画で公開中

実際に書いてみよう

今回のサンプルプログラムでは、エラトステネスのふるいを応用して素数判定を行います。

入力した数が素数か否か判定を行うため、探索リストを使わず、入力した数を割っていくことで素数かどうかを判定しています。

 

# 画面からの入力や終了を行う
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を使って機械学習の基礎を学ぶPythonオンライン講座を開催しています。

初心者向けの書籍を使って人工知能(AI)や機械学習について学ぶことができます。

現役エンジニアがパーソナルメンターとして受講生に1人ずつつき、マンツーマンのメンタリングで学習をサポートし、最短4週間で習得することが可能です。

また、現役エンジニアから学べる無料のプログラミング体験会も実施しているので、ぜひ参加してみてください。