判断一个大于3的整数n是否为素数
时间: 2023-09-18 18:11:40 浏览: 73
C语言程序设计-从键盘输入一个大于3的整数,调用函数fun判断其是否素数,然后在main函数中输出相应的结论信息;
5星 · 资源好评率100%
好的,判断一个大于3的整数n是否为素数的方法一般有两种:
1.试除法:从2到n-1逐一试除,如果能整除,则不是素数,否则是素数。
2.素数筛法:先将2到n-1的所有数列出来,从2开始,将2的倍数全部标记为非素数;然后从3开始,将3的倍数全部标记为非素数;接着从5开始,将5的倍数全部标记为非素数,以此类推。最后未被标记的数即为素数。
我这里提供一种基于试除法的Python实现:
```python
def is_prime(n):
if n <= 3:
return n > 1
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
```
你可以将要判断的整数n作为is_prime函数的参数,如果返回True,则是素数,否则不是素数。
阅读全文