定义一个空列表，双层循环实现。时间复杂高计算慢（时间复杂度为 O ( n 2 ) \mathrm{O}\left(\mathrm{n}^{2}\right) O(n2)）
def naive_prime(n):
result = []
for i in range(2, n+1):
if i == 2:
result.append(i)
continue
for j in range(2, i):
if i % j == 0:
break
else:
if j == i - 1:
result.append(i)
return result
[https://zh.wikipedia.org/wiki/埃拉托斯特尼筛法]
给出要筛数值的范围n，找出
n
\sqrt{n}
n
以内的素数
p
1
,
p
2
,
…
,
p
k
p_{1}, p_{2}, \dots, p_{k}
p1,p2,…,pk。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个素数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个素数5筛，把5留下，把5的倍数剔除掉；不断重复下去…。
如图：
图片来自 https://upload.wikimedia.org/wikipedia/commons/b/b9/Sieve_of_Eratosthenes_animation.gif
其时间复杂度为（
O
(
n
⋆
lg
lg
n
)
O\left(n^{\star} \lg \lg n\right)
O(n⋆lglgn)）
def my_prime(n):
is_prime = [True] * (n + 1)
for i in range(2, (int(n ** 0.5) +1)):
if is_prime[i]:
for j in range(i**2, n+1, i):
is_prime[j] = False
return [x for x in range(2, n) if is_prime[x]]
用上述两种算法求1到100，1到1000， 1到10000的所有质数，计算两种算法的运行时间，评价其性能
import matplotlib.pyplot as plt
import seaborn as sns
import time as tm
import numpy as np
def my_prime(n):
is_prime = [True] * (n + 1)
for i in range(2, (int(n ** 0.5) +1)):
if is_prime[i]:
for j in range(i**2, n+1, i):
is_prime[j] = False
return [x for x in range(2, n) if is_prime[x]]
def naive_prime(n):
result = []
for i in range(2, n+1):
if i == 2:
result.append(i)
continue
for j in range(2, i):
if i % j == 0:
break
else:
if j == i - 1:
result.append(i)
return result
n = [100,1000,10000]
naive_time = []
advanced_time = []
for i in n:
start_1 = tm.perf_counter()
naive_prime(i)
end_1 = tm.perf_counter()
naive_time.append(end_1 - start_1)
start_2 = tm.perf_counter()
my_prime(i)
end_2 = tm.perf_counter()
advanced_time.append(end_2 - start_2)
print('naive_time ->>>>>>>>', '\n', naive_time)
print('advanced_time_time ->>>>>>>>', '\n', advanced_time)
print('提速了',(np.array(naive_time) - np.array(advanced_time)) / np.array(advanced_time))
fig = plt.figure(figsize=(10,6))
time = [naive_time, advanced_time]
colors = ['red', 'blue']
label = ['naive_prime', 'advanced_prime']
for i in range(2):
plt.plot(n, time[i], c=colors[i], label=label[i])
plt.scatter(n, time[i], c=colors[i])
#添加图例，loc='upper left表示图例位置在最左侧，一般也可以直接使用loc='best'
plt.legend(loc='upper left')
plt.xlabel('number')
plt.ylabel('running time')
plt.title('velocity of two algorithm')
plt.show()