はじめに
こんにちは、村田です。
同僚に出題した下記問題の解説です。
ユーザから整数の入力を受け取り、その整数が素数（prime number）であるかどうかを判断するプログラムを作成してください。入力された整数が素数であれば、"Yes, it is a prime number."と表示し、素数でなければ、"No, it is not a prime number."と表示してください。ヒント：2と3と6k±1
まず回答
def is_prime(n):
if n <= 1:
return False
elif n <= 3:
return True
elif n % 2 == 0 or n % 3 == 0:
return False
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True
n = int(input("Enter a number: "))
if is_prime(n):
print("Yes, it is a prime number.")
else:
print("No, it is not a prime number.")
このプログラムでは、まずis_primeという関数を定義して、入力された整数が素数かどうかをチェックしています。この関数は、素数が1またはそれ自体以外には約数を持たない特性を利用しています。その後、ユーザから整数の入力を受け取り、その入力が素数であるかどうかを表示します。（ユーザーは必ず自然数を入力してくれるという信頼に依っています、、）
途中のwhileの解説
このコードブロックは、与えられた数が素数であるかどうかを効率的に判断するためのものです。特に、このコードは6k ± 1形式の最適化を利用して、素数判定の速度を向上させています。
まず、素数は6k ± 1形式で表現できることを理解することが重要です。なぜなら、2と3の倍数以外のすべての数（つまり、6k ± 1形式で表現できる数）だけをチェックすれば、それが素数かどうかを判断できるからです。
コードの詳細は以下のとおりです：
i = 5
iを5に初期化します。このコードの前に、関数は既に2と3で割り切れるかどうかをチェックしています。ここからは6k-1形式で最初の数（k = 1のとき）をチェックします。
while i * i <= n
素数判定では、与えられた数（この場合はn）の平方根までチェックするだけで十分であるため、iの値がnの平方根を超えるまでループを続けます。これは効率化の一環です。
if n % i == 0 or n % (i + 2) == 0
ここで、数nが6k ± 1形式の数（つまり、i（6k-1）とi+2（6k+1））で割り切れるかどうかをチェックします。もし割り切れる場合、その数nは素数ではありません。
i += 6
6k ± 1形式の次の数に移動します。最初のiは5（61 - 1）、次は11（62 - 1）、次は17（6*3 - 1）となります。
return True
nが素数である場合、この行に到達します。すなわち、2や3、または任意の6k ± 1形式の数で割り切れない場合、nは素数であると判断されます。
このように、このコードブロックは素数判定をより効率的に行うための一部です。
おまけの証明
2と3を除くすべての素数が、形式6k ± 1の数であるということを証明します。ここで、kは0より大きい整数です。
まず、任意の正の整数nは、6で割った余りにより次の6つの形式のいずれかで表すことができます：
6k (余り 0) 6k + 1 (余り 1) 6k + 2 (余り 2) 6k + 3 (余り 3) 6k + 4 (余り 4) 6k + 5 (余り 5) これらのうち、形式1、3、4の数はそれぞれ6、2、3で割り切れるので、これらは素数であることはありません（素数は1と自分自身以外の数で割り切れないので）。したがって、素数は形式2、5、6（すなわち6k + 1、6k + 4 = 6(k + 1) - 2、6k + 5 = 6(k + 1) - 1）のいずれかになります。
しかし、形式5の数（6k + 4 = 6(k + 1) - 2）は2で割り切れるため、これも素数ではありません。したがって、2と3を除くすべての素数は、形式2または6（すなわち6k + 1または6(k + 1) - 1）のいずれか、つまり6k ± 1の形式になります。
以上により、2と3を除くすべての素数が6k ± 1形式の数であることが証明されました。
おわりに
数学の証明問題をプログラムに落とすのって楽しいですね。