素数判断python
时间: 2023-11-08 10:03:57 浏览: 57
判断一个数是否为素数,可以使用如下的 Python 代码:
```python
def is_prime(n):
if n < 2:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
```
这个函数的实现采用了试除法,时间复杂度是 $O(\sqrt{n})$。
相关问题
判断素数的python代码
以下是三种判断素数的Python代码:
方法一:
```python
n = int(input("输入一个正整数:"))
yes = 1
for i in range(2, n):
if n % i == 0:
yes = 0
break
if yes:
print(n, '是素数')
else:
print(n, '不是素数')
```
方法二:
```python
m = int(input('输入一个正整数:'))
i = 2
while i < m:
if m % i == 0:
break
i += 1
if i > m:
print(m, '是素数')
else:
print(m, '不是素数')
```
方法三:
```python
from math import sqrt
n = int(input('请输入一个正整数:'))
i = 2
k = int(sqrt(n))
while i <= k:
if n % i == 0:
break
i += 1
if i > k:
print(n, '是素数')
else:
print(n, '不是素数')
```
Python素数判断
Python素数判断可以使用以下两种方法:
1. 质数判断法:
一个数如果只能被1和它本身整除,那么这个数就是质数。通过遍历2到该数-1的所有数,判断是否能被整除,来判断该数是否为质数。
代码示例:
```python
def is_prime(num):
if num < 2:
return False
for i in range(2, num):
if num % i == 0:
return False
return True
```
2. 厄拉多塞筛法:
该算法是在一定范围内筛选出所有的质数,而不是单独判断一个数是否为质数。首先将2到n的正整数放入表中,然后在2的上面画一个圆圈,然后把表中所有2的倍数都划掉;第一个既没有画圈又没有被划去的数是3,将它画圈,再把表中所有3的倍数都划去;接下来是5、7、11等质数,不断重复这个过程,直到筛完为止。
代码示例:
```python
def sieve_of_eratosthenes(num):
primes = [True] * (num+1)
primes, primes = False, False
for i in range(2, int(num ** 0.5) + 1):
if primes[i]:
for j in range(i*i, num+1, i):
primes[j] = False
return [i for i in range(num+1) if primes[i]]
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![py](https://img-home.csdnimg.cn/images/20210720083646.png)
![py](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)