猫史档案馆

鸽了将近一天，今天来着重探讨一下关于时间上的优化

接上文

四   时间复杂度优化

（一）缩减范围

我们都知道，一个合数一定能被分解成类似c=a*b（1<a<=b<=c)的形式，因此我们得知，一个合数只要找到最小因子a那么已经可以确定c是合数。因此在极限状态(指a=b)下c以内的素数只需要筛到根号c即可。

代码如下:

import math,time
d=int(input())
t1=time.time()
c=[False]*(d+1)
for i in range(2,d+1):
    if not c[i]:
    print(i,end=' ')
    if i<=math.sqrt(d)+1:
        for j in range(1,d//i+1):
            c[i*j]=True
t2=time.time()
print(t2-t1)
time.sleep(10)

这时d=10000000时仅需约3秒，但这还不是极限。

（二） 只筛奇数

这个改进很容易想到，因为素数除了二以外，其它都是奇数，所以可以因此进行优化。即特判二，将寻找的部分步长改为2。

import math,time
d=int(input())
t1=time.time()
c=[False]*(d+1)
print(2,end=' ')
for i in range(3,d+1,2):
    if not c[i]:
    print(i,end=' ')
    if i<=math.sqrt(d)+1:
        for j in range(2,d//i+1):
            c[i*j]=True
t2=time.time()
print(t2-t1)
time.sleep(10)

当d=10000000时用时约2.45秒，和欧拉筛所用的时间相同，但这还不是极限。

（三） 排除一切偶数

其实从上一优化中看出：我们实际上已经不会去选择偶数了，通过数的奇偶性质，我们可以得出只有奇数*奇数=奇数，所以我们可以从奇数开始考虑

从第一次优化中我们可以逆推出：任意平方数p²一定已经把小于等于p²的素数筛出了，因此在任意情况下只要从i²（现在所选的素数的平方）开始找素数即可，又因为目前考虑的素数一定是奇数。所以综上，可以进行以下的修改：

import math,time
d = int(input())
t1=time.time()
c = [False]*(d+1)
print(2, end=' ')
for i in range(3, d+1, 2):
    if not c[i]:
    print(i, end=' ')
    if i<=math.sqrt(d)+1:
        for j in range(i, d//i+1, 2):
            c[j*i] = True
t2=time.time()
print(t2-t1)
time.sleep(10)

当d=10000000时 用时1.8秒

（四）内循环优化

 原本到第三步优化时，我认为这就是埃氏筛的极限了，但我与另外一位作者聊天时，这个想法就诞生了。

Python的列表中有一个内置函数list[start:end:step]，其中默认start=0，end=列表长度，step=1,这个函数可用于切片和多重赋值。如在列表list[1,2,3,4]中，我们可以通过list[::2]=[6，7]使得列表变成list[6,2,7,4]因此，通过这个特性，我们可以再一次将内循环省略。（其实是因为Python中循环效率太慢了，只要能找到替换的，一般都要快）

import math,time
d = int(input())
t1=time.time()
c = [False]*(d+1)
print(2, end=' ')
for i in range(3, d+1, 2):
    if not c[i]:
        print(i, end=' ')
        if i<=math.sqrt(d)+1:
            c[i::2*i]=[True]*((d+i)//(2*i))
t2=time.time()
print(t2-t1)
time.sleep(10)

当d=10000000时 用时1.3秒，又快了0.5秒

（四）减少不必要的if

(本来这一篇是打算放到一些疑问里的，不过今天要把时间优化讲完就直接再这里说了）

经过测试，虽然埃氏筛在优化过后效率比欧拉筛要高的多。但是单单比较筛选次数，欧拉筛还是远高于埃氏筛（d=10000000时，欧拉筛4335421次，而埃氏筛8925144次），我想其原理是在欧拉筛中有两个循环内的if语句被执行太多次，而只有一次生效。也就是说程序用了很多时间处理了一些不必要的语句，造成了时间“浪费”，所以即使是埃氏筛（优化过后）比欧拉筛多筛了一倍，但是速度还是比其快了一倍

依此原理，我们还能给出一个优化，即将小于等于sqrt(d)的部分不变，然后将大于sqrt(d)的所有数字放到另外一个循环中，让程序减少大量的判断时间。

import math
import time
import math, time
d = int(input())
t1 = time.time()
c = ([False] * (d + 1))
f = int((math.sqrt(d)))
print(2)
for i in range(3, (f + 2), 2):
    if not (c[i]):
        print(i)
        c[i*i::2*i] = [True]*((d-(i-2)*i)//(2*i))
if (f % 2 == 0):
    f += 1
for i in range((f + 2), (d + 1), 2):
    if not (c[i]):
        print(i)
t2 = time.time()
print((t2 - t1))
time.sleep(10)

d=10000000时 只需1秒

至此埃氏筛的时间优化结束，下一篇说一说空间上的优化。