python质数判断
时间: 2024-05-30 15:07:15 浏览: 18
Python中判断质数的方法有很多种,这里介绍两种简单的方法。
方法一:暴力枚举
遍历2到n-1的所有数,判断n是否能被整除,如果能则不是质数,否则是质数。
代码如下:
```
def is_prime(n):
if n <= 1:
return False
for i in range(2, n):
if n % i == 0:
return False
return True
```
方法二:优化枚举
在暴力枚举的基础上,可以进一步优化,只需要遍历2到n的平方根即可。
代码如下:
```
import math
def is_prime(n):
if n <= 1:
return False
for i in range(2, int(math.sqrt(n))+1):
if n % i == 0:
return False
return True
```
相关问题
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]]
```
python素数判断
以下是Python中判断素数的五种实现方式:
1.暴力判断法
```python
def is_prime(n):
if n < 2:
return False
for i in range(2, n):
if n % i == 0:
return False
return True
```
2.平方根暴力判断法
```python
import math
def is_prime(n):
if n < 2:
return False
for i in range(2, int(math.sqrt(n))+1):
if n % i == 0:
return False
return True
```
3.素数表筛选法
```python
def get_primes(n):
primes = []
for i in range(2, n+1):
is_prime = True
for j in primes:
if i % j == 0:
is_prime = False
break
if is_prime:
primes.append(i)
return primes
```
4.埃拉托斯特尼(Eratosthenes)筛法
```python
def get_primes(n):
primes = [True] * (n+1)
primes[0] = primes[1] = False
for i in range(2, int(n**0.5)+1):
if primes[i]:
primes[i*i: n+1: i] = [False] * len(primes[i*i: n+1: i])
return [i for i in range(n+1) if primes[i]]
```
5.欧拉(Euler)筛法
```python
def get_primes(n):
primes = []
is_prime = [True] * (n+1)
for i in range(2, n+1):
if is_prime[i]:
primes.append(i)
for j in primes:
if i*j > n:
break
is_prime[i*j] = False
if i % j == 0:
break
return primes
```
相关推荐
![py](https://img-home.csdnimg.cn/images/20210720083646.png)
![py](https://img-home.csdnimg.cn/images/20210720083646.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)