用莱梅检验法编写判断素数的程序 python
时间: 2024-06-15 21:08:56 浏览: 13
莱梅检验法(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`。
你可以通过输入一个整数来测试这个程序,程序会输出该数是否为素数。