python用莱梅检验法编写判断素数的程序
时间: 2024-06-15 11:08:55 浏览: 13
莱梅检验法(Lehmer's primality test)是一种用于判断一个数是否为素数的方法。下面是使用Python编写的莱梅检验法判断素数的程序:
```python
def lehmer_test(n):
if n < 2:
return False
if n == 2 or n == 3:
return True
if n % 2 == 0 or n % 3 == 0:
return False
i = 5
w = 2
while i * i <= n:
if n % i == 0:
return False
i += w
w = 6 - w
return True
# 测试
num = int(input("请输入一个整数:"))
if lehmer_test(num):
print(num, "是素数")
else:
print(num, "不是素数")
```
相关问题
用莱梅检验法编写判断素数的程序 python
莱梅检验法(Lehmer's primality test)是一种用于判断一个数是否为素数的方法。下面是一个用Python编写的莱梅检验法判断素数的程序:
```python
def is_prime(n):
if n <= 1:
return False
if n <= 3:
return True
if n % 2 == 0 or n % 3 == 0:
return False
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True
# 测试代码
num = int(input("请输入一个整数:"))
if is_prime(num):
print(num, "是素数")
else:
print(num, "不是素数")
```
这个程序中的`is_prime`函数接受一个整数作为参数,返回一个布尔值,表示该整数是否为素数。程序首先判断输入的数是否小于等于1,如果是,则直接返回`False`。然后判断输入的数是否小于等于3,如果是,则直接返回`True`。接下来,程序使用莱梅检验法进行判断,具体步骤如下:
1. 判断输入的数是否能被2或3整除,如果能,则直接返回`False`。
2. 初始化一个变量`i`为5,从5开始进行循环。
3. 在循环中,判断`i`是否平方大于等于输入的数,如果是,则跳出循环。
4. 在循环中,判断输入的数是否能被`i`整除或者能被`i+2`整除,如果是,则返回`False`。
5. 在循环中,每次将`i`增加6,因为素数的特性是除了2和3之外,其他素数都可以表示为6的倍数加减1。
6. 如果循环结束后都没有返回`False`,则说明输入的数是素数,返回`True`。
你可以通过输入一个整数来测试这个程序,程序会输出该数是否为素数。
python用埃拉托斯特尼筛法编写判断素数的程序
埃拉托斯特尼筛法(Sieve of Eratosthenes)是一种用于判断素数的经典算法。下面是使用Python编写的埃拉托斯特尼筛法判断素数的程序:
```python
def sieve_of_eratosthenes(n):
# 创建一个长度为n+1的布尔数组,用于标记数字是否为素数
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
# 从2开始遍历到根号n
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
# 将i的倍数标记为非素数
for j in range(i * i, n + 1, i):
is_prime[j] = False
# 收集所有素数
primes = [i for i in range(n + 1) if is_prime[i]]
return primes
# 示例:判断100以内的素数
primes = sieve_of_eratosthenes(100)
print(primes)
```
这段代码使用了一个布尔数组 `is_prime` 来标记数字是否为素数。首先将数组中的所有元素初始化为 `True`,然后从2开始遍历到根号n,如果当前数字是素数,则将其倍数标记为非素数。最后,收集所有标记为素数的数字,即为所求的素数列表。