定义一个空列表，双层循环实现。时间复杂高计算慢（时间复杂度为 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)continuefor j in range(2, i):if i % j == 0:breakelse:if j == i - 1: result.append(i)return result 2. csdsp筛法[https://zh.wikipedia.org/wiki/csdsp筛法]
给出要筛数值的范围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 ) Oleft(n^{star} lg lg nright) O(n⋆lglgn)）
用上述两种算法求1到100，1到1000， 1到10000的所有质数，计算两种算法的运行时间，评价其性能
第一中算法花费的时间分别为[ 0.0001109 , 0.008414699999999999 , 0.609495 ] [0.0001109,0.008414699999999999,0.609495] [0.0001109,0.008414699999999999,0.609495]第二种算法花费的时间分别为
[ 1.4600000000000003 e − 05 , 0.0001021000000000008 , 0.0010745000000000893 ] [1.4600000000000003 e-05,0.0001021000000000008,0.0010745000000000893] [1.4600000000000003e−05,0.0001021000000000008,0.0010745000000000893]
分别提速了
[ 6.80555556 83.48502994 551.70287728 ] left[begin{array}{ccc}{} & {6.80555556} & {83.48502994} & {551.70287728 ]}end{array}right. [6.8055555683.48502994551.70287728]
程序汇总 import matplotlib.pyplot as pltimport seaborn as snsimport time as tmimport numpy as npdef 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)continuefor j in range(2, i):if i % j == 0:breakelse: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()