素数とは
素数とは、（異なる正の）約数が2個しかない自然数のことです。
2以上の整数では、どれも1とその数自身の2つは必ず約数になります。素数は、約数が2つしかありません。それ以外に約数を持つものは、素数の倍数になり、合成数と呼ばれます。1は、約数が1個だけなので素数ではありません。1が素数でないのには理由があります。それは、もし1を素数にしてしまうと、すべての自然数が合成数になってしまうからです。
ちなみに自然数は0以上の整数（非負整数）とすることもありますが、いずれにせよ0は素数ではありません。
素数判定のプログラムを作る
整数nを入力し、それが素数の場合はTrue、素数でない場合はFalseを表示します。最終目標は自然数以外の整数にも対応することです。
試作
自然数はほぼすべて1とその数自身の2つが約数になるので、2からn-1までをチェックして、割り切れる数が1つもなければOKです。
ということで作ってみたのがこちらです。
test.py
n = int(input())
b = False
for i in range(2, n):
if n % i == 0:
break
elif i == n - 1:
b = True
print(b)
しかし、これには問題点があります。
for文の範囲はrange(2, n)となっているので、nが3以上でないと実行されません。つまりn = 2のときにはFalseとなってしまいます。
素数判定1
試作を修正したものです。n = 2のときは、初めからbをTrueにしておきます。
prime1.py
n = int(input())
b = bool(not(n - 2))
for i in range(2, n):
if n % i == 0:
break
elif i == n - 1:
b = True
print(b)
素数判定2 ｜コードを短くする
range(2, n)とすると、コードが長くなってしまうので、range(1, n)に変更して書き直します。できるだけ短くなるようにしてみました。
prime2.py
n = int(input())
b = -1
for i in range(1, n):
if n % i == 0:
b += 1
print(bool(not b))
素数判定3 ｜処理を少なくする
素数判定2では、偶数であっても、2からn - 1まで1つづつ全部チェックを行うので、大きな整数では時間がかかります。そこで、素数判定1をもとに処理を減らせるように修正しました。コードは素数判定2よりも少し長くなりますが、計算時間は短くなります。
prime3.py
n = int(input())
b = bool(not(n - 2))
a = (n + 1) // 2
for i in range(2, a + 1):
if n % i == 0:
break
elif i == a:
b = True
print(b)
また新たなコードを思いついたら更新します。