Python第21题：判断一个数是否为素数

题目

从标准输入读入一个整数 n，判断其是否为质数（素数）。质数是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的数。

输入格式：一行输入一个整数 n。

输出格式：若是素数输出 yes，否则输出 no，末尾换行。

数据范围与约定：-10⁹ ≤ n ≤ 10⁹。

思路与算法

1. 小于 2 的整数拦截
所有小于等于 1 的整数都不是素数；2 是最小的素数，也是唯一的偶素数。

2. 试除边界 √n 优化
因数成对分布于 √n 左右两侧。循环试除只需检查 i * i <= n，一旦整除即可直接判定合数并退出，时间复杂度为 O(√n)。

完整程序

n = int(input())

# 试除法判断素数：小于 2 的数不是素数
if n < 2:
    print('no')
else:
    is_p = True
    # 只需试除到根号 n
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            is_p = False
            break
    print('yes' if is_p else 'no')

运行示例

输入：

17

输出：

yes