质数是指只能被1和自身整除的正整数，在数学的世界中有着重要的应用，如RSA加密算法、素数筛法等 。在实际应用中，我们需要经常挑选出一定范围内的质数，这就需要用到计算机编程语言来实现 。Python作为一种高级编程语言，具有简单易学、高效易用、扩展性强等优点，自然而然成为了编写质数筛法的首选语言之一 。
一、常规方法
文章插图
最简单的方法是暴力枚举法，即从2开始，依次判断每一个数是否是质数 。如果一个数是质数，那么它一定不能被比它小的整数整除，因此可以用循环来实现 。具体实现如下：
```python
def prime1(n):
prime_list = []
for i in range(2, n+1):
flag = True
for j in range(2, i):
if i % j == 0:
flag = False
break
if flag:
prime_list.append(i)
return prime_list
```
该方法的时间复杂度为O(n^2)，效率较低，不适用于大量数据的处理 。
二、优化方法
1. 去掉偶数
首先，我们可以去掉偶数，因为除了2以外，所有的偶数都不是质数 。所以，我们可以先判定2是否是质数，然后从3开始，每次增加2，依次判断每一个奇数是否是质数 。具体实现如下：
```python
def prime2(n):
prime_list = []
if n < 2:
return prime_list
prime_list.append(2)
for i in range(3, n+1, 2):
flag = True
for j in range(2, int(i**0.5)+1):
if i % j == 0:
flag = False
break
if flag:
prime_list.append(i)
return prime_list
```
2. 去掉偶数和倍数
其次，我们可以将判断的范围缩小到[2, n/2]，因为如果一个数大于n/2，那么它就不能是n的因数 。还可以进一步优化，去掉所有偶数的倍数，因为偶数的倍数一定是偶数，已经在判断2的时候去掉了，不必再判断一次 。具体实现如下：
```python
def prime3(n):
prime_list = []
if n < 2:
return prime_list
prime_list.append(2)
for i in range(3, n+1, 2):
flag = True
for j in range(3, int(i**0.5)+1, 2):
if i % j == 0:
flag = False
break
if flag:
prime_list.append(i)
return prime_list
```
3. 去掉偶数和倍数（优化版）
最后，我们可以再进一步优化，去掉所有偶数的倍数和3的倍数，因为3的倍数已经被偶数的倍数包含了 。具体实现如下：
```python
def prime4(n):
prime_list = []
if n < 2:
return prime_list
prime_list.append(2)
prime_list.append(3)
for i in range(5, n+1, 6):
flag1 = True
flag2 = True
for j in range(2, int(i**0.5)+1):
if i % j == 0:
flag1 = False
break
if flag1:
prime_list.append(i)
for j in range(2, int((i+2)**0.5)+1):
if (i+2) % j == 0:
flag2 = False
break
if flag2 and i+2 <= n:
prime_list.append(i+2)
return prime_list
```
该方法的时间复杂度为O(n^(3/2))，效率较高，可以处理较大的数据 。
三、测试结果
我们可以用time库来测试不同方法的运行时间，从而比较它们的效率 。具体代码如下：
```python
import time
n = 100000
start = time.time()
prime1(n)
end = time.time()
print("prime1:", end-start)
start = time.time()
prime2(n)
end = time.time()
print("prime2:", end-start)
start = time.time()
prime3(n)
end = time.time()
print("prime3:", end-start)
start = time.time()
prime4(n)
end = time.time()
print("prime4:", end-start)
```
运行结果如下：
```
prime1: 16.877270221710205
推荐阅读
- 如何挑选防晒衣？防晒衣真的防晒吗？
- python input函数如何不要引号？
- python time.asctime如何返回字符串？
- python实现数独算法实例
- python对数组进行反转的方法
- 通过C++学习Python
- Python xlrd读取excel日期类型的2种方法
- python3如何改变默认的ascii编码?？
- Python函数嵌套如何快速掌握使用？
- python三元操作符如何赋值？