Python:素数の判定

Question

素数の判定をしたのですが模範解答は次のようなコードになっていて理解できない部分がありました。

n_list= range(2,11)

for i in range(2, int(10**0.5)+1):
    n_list=[x for x in n_list if (x==i or x%i != 0)]
    
for j in n_list:
    print(j)

コード

コード内のint(100.5)の意味が理解できませんでした。
1、intがなぜこの場所に入るのか
2、なぜ100.5をする必要があるのか

の2点が不明です。

お教えいただければ幸いです。

Answer 1

素数は、「1と自分自身以外に約数を持たない数」ですが、約数は自分自身以下なので、文字通りプログラムにすると、「2以上自分自身未満の整数で割り切れるかどうか」を判断することになります。

が、もし数xがmとnで割り切れて、x = m * nのように書けたとすると、ちょっと考えれば分かりますが、mとnの少なくとも一方はxの平方根以下です。

つまり、「2以上自分自身の平方根以下の整数で割り切れるかどうか」を調べれば良いことになります。

あとは、高速化のために、「2以外の偶数で割ってみる必要は無い」とか、「3以外の3の倍数で割ってみる必要は無い」とか。いろいろ。

Answer 2

1、intがなぜこの場所に入るのか

range()関数の引数は整数のシーケンスでなければならないからです。

10**0.5≒3.16227766...と小数なので、そのままではエラーになるからです。

2、なぜ10**0.5をする必要があるのか

計算回数を減らすためです。

2以上の整数aが素数であるか判定するためには、まず2から√a以上の最小の整数で割り切れないことを判定すればよく、
2からaまでの数を使って判定する必要はありません。（その数自身で割り切れる場合を除く）

なぜならば、aが√aよりも大きい整数で割り切れたならば、その商は、√aより小さいはずだからです。

int(√112)+1＝11

112÷7＝16

112÷16＝7　　<==11より大きい数を調べなくてもよい

(上の等に「すでに7で割り切れることがわかっているから」）