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

前提

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

疑問点

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

python
1for i in range(2, 101):
2    for j in range(2, i):
3        if i % j == 0:
4            break
5    else:
6        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より小さい自然数」が存在し得ないためこのような問題が発生してしまうのだと思われます。実際に実用的かはともかくとして、このなんとなく気持ち悪い部分をスマートに解消するようなアルゴリズム・コードを上手いこと組めないものでしょうか？

行動規範の内容に同意します

回答7件

ベストアンサー

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

言語の仕様だからです。
https://docs.python.org/ja/3/reference/compound_stmts.html#the-for-statement

全ての要素を使い切ったとき (シーケンスが空であったり、イテレータが StopIteration 例外を送出したときは、即座に)、 else 節があればそれが実行され、ループは終了します。

ここにあるように、for文のシーケンス(range()で表されるところ)が空だった場合、elseがあればそれを実行して終了することになっているのです。

「1より大きく2より小さい自然数」が存在し得ないためこのような問題が発生してしまうのだと思われます。実際に実用的かはともかくとして、このなんとなく気持ち悪い部分をスマートに解消するようなアルゴリズム・コードを上手いこと組めないものでしょうか？

気持悪いのはそのとおりかもしれませんね。

であれば、「2」は特殊な素数ということにして、あらかじめリストの先頭に入れておいて、「for i in range(3, 101):」として、3からチェックするようにするのはどうでしょうか？

また、これは、range()関数の仕様から来ているとも言えます。もし、rangex(a, b)という「aより大きく、bより小さい数を列挙する」関数があれば、「for j in rangex(1, j):」という書き方ができて気持悪さは減りますか？

投稿2022/10/05 05:33

TakaiY

総合スコア12765

range(2,2)においてjに何が代入され

代入コード自体が実行されません。

range(2, 2)で生成するシーケンスは空なので、ループは1度も実行されません。もちろん、割り算や余りを考える余地もありません。

投稿2022/10/05 05:19

編集2022/10/05 05:22

maisumakun

総合スコア145184

maisumakun

2022/10/05 05:21

> このなんとなく気持ち悪い部分をスマートに解消するようなこのコードがむしろスマートだと判断します。（もっとも、n-1まで割り続けるのは無駄が多すぎるので、実用目的であればもっと別なコードを使うべき場面ではあります）

行動規範の内容に同意します

「1より大きくその数より小さい自然数では割り切れないとき素数と判定する」

は、2を特別扱いせずに他のケースと同じロジックで判断できるスマートな方法だと思います。
これを気持ち悪いと思わない方が良いです。

プログラムを設計するときに、端っこの状態を特別扱いしたくなることが、まま、ありますが、うまく工夫すると特別扱いをせずに済み、ループ内のif文を1つか2つ減らすことが出来ます。

説明部分には「2から順番に割り算を繰り返し、元の数より1小さい数になっても割り切れなかったら素数と判定する」みたいなことが書かれていることが多いです。

は、ご指摘の通り不正確な表現ですね。初心者向けの説明だからでしょうか。

投稿2022/10/05 08:11

otn

総合スコア84555

8.3. for 文

全ての要素を使い切ったとき (シーケンスが空であったり、イテレータが StopIteration 例外を送出したときは、即座に)、 else 節があればそれが実行され、ループは終了します。
最初のスイートの中で break 文が実行されると、 else 節のスイートを実行することなくループを終了します。

と記載があるように、シーケンスが空の場合もすべての要素を使い切ったときと同じ処理になります。

すなわち
i=3のときは、すべての要素を使い切る(途中でbreakが実行されない)のでelse節が実行されます。
i=2のときも、シーケンスが空なので、これも同じくelse節が実行されます。

投稿2022/10/05 05:31

can110

総合スコア38266

Pythonでは世にも珍しいfor-else文が使えるため，上のようになっています．for文の中でbreakされなかった場合にelseに入るというものです．これがない言語では，次のように書く必要がありました．

python
1for i in range(2, 101):
2    divided = False
3    for j in range(2, i):
4        if i % j == 0:
5            divided = True
6            break
7    if not divided:
8        print(i)