)编写通过将正整数 n 对 2, 3, …, n-1 逐个取模,判断其是否为素数的方法
时间: 2024-09-18 13:18:09 浏览: 43
Python编程判断一个正整数是否为素数的方法
5星 · 资源好评率100%
为了编写一个检查一个正整数 n 是否为素数的方法,我们可以采用一种称为“试除法”的传统算法。这里是一个简单的步骤:
1. **定义函数**:创建一个名为 `is_prime` 的函数,它接受一个正整数 `n` 作为输入。
2. **基础情况**:
- 如果 `n` 小于 2,返回 False,因为素数定义为大于 1 的自然数。
- 如果 `n` 等于 2 或 3,这是最小的两个素数,直接返回 True。
3. **循环遍历**:从 2 开始,到 `n-1` 结束(不包括 n),依次对 `n` 取模。如果存在任何一个 `i`(2 <= i < n),使得 `n % i == 0`,说明 n 不是素数,因为可以被整除,所以返回 False。
4. **循环结束后的判断**:如果没有找到能整除 n 的因子,那么 n 可能是素数,返回 True。
以下是这个方法的伪代码示例:
```python
def is_prime(n):
if n < 2:
return False
elif n == 2 or n == 3:
return True
for i in range(2, int(n**0.5) + 1): # 避免检查大于 n^(1/2) 的因子,效率更高
if n % i == 0:
return False
return True
```
阅读全文