質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
86.12%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

解決済

range関数と素数判定アルゴリズム

C_minor_seventh
C_minor_seventh

総合スコア8

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

7回答

0リアクション

0クリップ

321閲覧

投稿2022/10/05 05:01

前提

pythonにおけるrange関数についての質問です。

疑問点

まずは以下のコードをご覧ください。

python

for i in range(2, 101): for j in range(2, i): if i % j == 0: break else: print(i)

このプログラムは100以下のいわゆる素数を列挙する単純なプログラムで、実際この通りに実行しても問題なく動き期待通りの結果を吐き出すことが確認できます。しかし改めてデバッグモードで1行ずつ送っていくと、iが2の時に限りよくわからない挙動をしているように見えます。

i = 2 のとき2行目にあるrange関数はrange(2,2)という形になるわけですが、このときjに代入される具体的な数は明らかに存在せず、本来であれば i % j という計算を実行することすら不可能なはずです。しかし実際にはこのコードはエラーを吐くこともなく突然elseへと飛び、print(i)で2をアウトプットしてそそくさと i = 3 の場合の計算へと入っていきます。

なぜこのようなことが起きるのでしょうか?range(2,2)においてjに何が代入され、i % j の計算結果はどうなって、どういう条件式のもとで2が吐き出されるのでしょうか?そもそもrange関数はどういったコードで成り立っているのでしょうか?

ごく初歩的な質問で申し訳ありませんが、ご教示いただければ幸いです。

蛇足

pythonにかぎらずもう少し拡張した話になります。こちらについても見解をいただければ嬉しいですが、あくまで蛇足ですのでプログラミングに直接関係ないとご判断されるようでしたら無視していただいて構いません。

上記のコードはよく初心者向けのサイトなどによく使われており、説明部分には「2から順番に割り算を繰り返し、元の数より1小さい数になっても割り切れなかったら素数と判定する」みたいなことが書かれていることが多いです。
しかしこれもよくよく考えるとちょっと変で、最小の素数である"2"に限ってはまず一番最初に割り切れるかを試す"2"で割り切れてしまうため、素直に文面通りにアルゴリズムを組むと合成数と判定されてしまいます。また「元の数より1小さい数」は"1"であり、原文をそのまま解釈すると「2から1まで順番に数を大きくしていって割り切れるか試す」という全く意味の通らないアルゴリズムになってしまいます。

本来素数と判定するためには「1からその数まで順番に割っていき、1とその数自身でのみ割り切れたとき素数と判定する」というアルゴリズムが必要なはずで、多くのコードではこれを「1より大きくその数より小さい自然数では割り切れないとき素数と判定する」というアルゴリズムで実装しているのだと思いますが、こと"2"に限っては「1より大きく2より小さい自然数」が存在し得ないためこのような問題が発生してしまうのだと思われます。実際に実用的かはともかくとして、このなんとなく気持ち悪い部分をスマートに解消するようなアルゴリズム・コードを上手いこと組めないものでしょうか?

以下のような質問にはリアクションをつけましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

リアクションが多い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

下記のような質問は推奨されていません。

  • 間違っている
  • 質問になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

適切な質問に修正を依頼しましょう。

まだ回答がついていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
86.12%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。