如何判断一个数是否为素数?

素数是只由 1 和它本身的整数倍组成的数。

素数判定算法

1. 初始化：

   • 设 is_prime 为 True，表示该数是素数。
   • 设置 i 为 2，因为 1 不是素数。

2. 循环：

   • 对于 i 从 2 到 sqrt(i) 的每个整数：
     • 如果 i 整数被 num 整除，则 num 不是素数。
     • 否则，更新 is_prime 为 False。

3. 检查is_prime：

   • 如果 is_prime 为 True，则 num 是素数。

示例

def is_prime(n):
    is_prime = True
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            is_prime = False
            break
    return is_prime

使用示例

print(is_prime(13))  # 输出 True
print(is_prime(17))  # 输出 True
print(is_prime(1024))  # 输出 False

注意

• 由于素数的定义，所有素数都是大于 1 的，但所有大于 1 的整数都不是素数。
• 算法的效率取决于 num 的大小，素数检测算法的平均时间复杂度为 O(sqrt(n))。