判断一个大于 2 的正整数 n 是否为素数,请用至少两种方法实现。
时间: 2024-05-10 10:17:46 浏览: 14
方法一:试除法
试除法是素数判断的一种基本方法,即用 2 到 sqrt(n) 之间的所有正整数去除 n,若都无法整除,则 n 是素数,否则 n 不是素数。
代码实现:
```python
import math
def is_prime(n):
if n <= 1: # 1 不是素数
return False
for i in range(2, int(math.sqrt(n))+1):
if n % i == 0:
return False
return True
```
方法二:埃氏筛法
埃氏筛法是一种更高效的素数筛法,其基本思想是从 2 开始,将每个素数的倍数都标记成合数,直到筛完所有小于等于 n 的素数。
代码实现:
```python
def is_prime(n):
if n <= 1: # 1 不是素数
return False
is_prime = [True] * (n+1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(math.sqrt(n))+1):
if is_prime[i]:
# 将 i 的倍数标记为合数
j = i * i
while j <= n:
is_prime[j] = False
j += i
return is_prime[n]
```
以上两种方法都可以判断一个大于 2 的正整数是否为素数。