素数の判定

与えられた数 n が素数なら True，そうでなければ False を返す関数を作ってみましょう。

基本は順に割っていけばよいはずです。

def isprime(n):
    if n < 2:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

動作確認してみましょう。

for i in range(2, 100):
    if isprime(i):
        print(i, "は素数")

上は 2 以上 n 未満の整数すべてで割ってみました。もっと節約できるでしょうか。

import math

def isprime(n):
    if n < 2:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0: return False
    return True

いろいろ改良ができそうです。例えば 2 を除けば偶数で割ってみる必要はないので，計算量は半分にできます。

import math

def isprime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0: return False
    return True

今日（例えば 20190823）は素数か？

import datetime

n = int(f"{datetime.datetime.now():%Y%m%d}")
isprime(n)

math.sqrt() は平方数については正確な平方根を与えるはずですが，浮動小数点数の精度を超える整数の場合は心配です。整数の平方根を整数の範囲で求める次の isqrt() を使えば万全です：

def isqrt(n):
    if n == 0:
        return 0
    x, y = n, (n + 1) // 2
    while y < x:
        x, y = y, (y + n // y) // 2
    return x

これを使った関数：

def isprime(n):
    if n < 2:
        return False
    for i in range(2, isqrt(n)+1):
        if n % i == 0:
            return False
    return True

もっと大きい数の素因数分解をするには，SymPy の数論ライブラリが便利です。

from sympy import factorint, isprime

factorint(5040)

{2: 4, 3: 2, 5: 1, 7: 1}

factorint(20190823)

{20190823: 1}

isprime(20190823)

True

問：2020年の大晦日と2021年の元日はともに素数です。3000年までにこのような年はどれくらいあるでしょうか。