欢迎来到雄杰鑫电商资讯网
技术教程

python判断是否为素数

冰川箭仙 次阅读
素数是只有1和它本身两个正因数的数；判断时先排除小于2的数，2是唯一偶素数，对n≥3只需试除到√n。

判断一个数是否为素数，核心是看它是否只有 1 和它本身两个正因数。最直接的方法是试除法：从 2 开始，检查到 √n（含）之间是否有能整除 n 的数。如果没有，就是素数。

基础实现（处理常见情况）

需要特别注意边界情况：小于 2 的数（如 0、1、负数）都不是素数；2 是最小的素数且是唯一的偶素数。

  • 若 n
  • 若 n == 2 → 返回 True
  • 若 n 是大于 2 的偶数 → 返回 False
  • 对奇数，只需检查 3 到 √n 之间的奇数即可

推荐写法（简洁高效）

以下函数兼顾可读性与效率：

def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    i = 3
    while i * i <= n:
        if n % i == 0:
            return False
        i += 2
    return True

用 i * i 替代 i 可避免浮点误差和类型转换，更安全。

小技巧：批量判断时可预处理

如果需频繁判断多个数（比如 1~1000 内），用埃氏筛法一次性生成布尔数组会更快：

# 生成 [0, n] 范围内是否为素数的列表
def sieve(n):
    is_prime_arr = [True] * (n + 1)
    is_prime_arr[0] = is_prime_arr[1] = False
    for i in range(2, int(n**0.5) + 1):
        if is_prime_arr[i]:
            for j in range(i*i, n+1, i):
                is_prime_arr[j] = False
    return is_prime_arr

使用示例：is_prime_arr = sieve(100); print(is_prime_arr[97])  # True

注意事项

  • Python 中整数无溢出问题，但大数（如 >10⁹）用试除法会变慢，此时建议用 Miller-Rabin 等概率算法
  • 输入应为整数，若传入浮点数（如 5.0），需先 int() 或加类型检查
  • 负数、0、1 均不是素数，这是数学定义，不要遗漏
python

相关文章

按ESC键退出。