素数の計算

素数は1と自分自身以外で割り切れない数です

import math
max=int(input('最大数'))
s=list()
for i in range(1,max+1):
    f=True
    sq=int(math.sqrt(i))
    for j in s[1:sq]:
        if i%j==0:
            f=False
            break
    if f:s.append(i)
print(s)

ｎが素数かどうかを確認するには1 ~ n-1までを順に割り
割り切れる数字があるかを確認します

①素数で割り切れるかを確認
２で割り切れる数は4,6,8・・・すべての2の倍数で割り切れます
同様に３で割り切れる数は6,9,12・・・で割り切れます
これを利用すると1 ~ n-1までのすべての素数で割ることで確認ができます

②nの平方根までを上限とする
100÷2=50 つまり100は51以上で割り切れることはありません
同様に100÷3＝33.3・・・　34以上で割り切れることがないことがわかります
これを繰り返し100÷10=10　11以上で割り切れないことがわかります
nの平方根より大きな数では割り切れることはありません

①と②を利用すると101が素数かどうか確認するためには
2,3,5,7で割り切れるかを確認することで素数確認ができます
2から100まで100回の割り算がたった4回の計算で確認ができるのは高速化、負荷低減に貢献します

平方根はn**0.5 pow(n,0.5) math.sqrt(n)などいろいろな方法で計算ができますが
math.sqrtが最も高速です