素数を生成する Python アルゴリズムの書き方

Pythonで素数を生成する方法にはいくつかあり、その一般的な2つの手法を以下に示します。

約数に割り切れるかどうかで判定する。割り切れれば素数ではない。

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

# 示例用法
print(is_prime(5))  # 输出 True
print(is_prime(10)) # 输出 False

方法2：平方根を利用する方法
このアルゴリズムは、ある数字が平方根以下となっている素数で割り切れるかどうかを判定することで素数であるかどうかを判定しています。これは、もしある数字が平方根以上の数で割り切れるとき、その数字は必ず平方根以下の素数で割り切れるからです。

import math

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

# 示例用法
print(is_prime(5))  # 输出 True
print(is_prime(10)) # 输出 False

いずれの方法でも素数判定は可能だが，特に多数の素数判定を行う必要がある場合には，後者の方式の方が効率が良いので，後者の方式が推奨される。