Python 素数判定

Number = int(input("please number >"))

for i in range(2,int(Number**(1/2)+1):
      if a%i == 0 :
            print("This number isn`t Primes.")
            print("At least , it cracked by",str(i))
            break
      else :
            print("This number is Primes !")   

素数の判定では、for文を使うのが良い。
今回は一工夫を加えることで、計算時間が短くなるようにした。原理は簡単だ。

与えた数字の平方根をとった値に1を足した整数までを割り続けることで、素数かを判定している。
もし、与えた整数が素数でなければ、必ずついとなる公約数が存在する。もし８を与えたなら、(1,8)(2,4)が対となる公約数である。このとき、8の平方根をとった値に1を足した整数を考えると、3となる。つまり、３まで順番に割り続ければ、必ず公約数に当たるはずである。それまでに公約数が見つからなければ、それは素数と言ってもよいだろう。