求十萬以內素數的兩種簡單優化（埃拉托色尼素數篩選法）

一、什麼是素數？

素數又稱為質數。素數定義為在大於1的自然數中，除了1和它本身以外不再有其他因數。素數在日常中最多的應用就是加密演算法，例如RSA加密演算法就是基於來實現的。RSA演算法會隨機生成兩個1024位的質數相乘，要破解密碼必須對乘積做質因數分解，而1024位的質因數分解是非常困難的。

二、如何快速的算出小於某個數的所有素數？

從素數的概念上似乎可以很快得出一個算素數的公式，即將一個數循環做除法，從1一直除到它本身，如果中途只有被1和自己整除了這個數便是素數了，這樣的計算效率是非常差的，因為他會不停的遍歷整個數據範圍。我們來試著跑一下它的效率：

#求10萬以內的素數
import datetime
start = datetime.datetime.now()
for i in range(2,100000):
for j in range(2,i):
if i%j == 0:
break
#else:
#print(i)
stop = datetime.datetime.now()
print(stop-start)

運行結果： 0:01:04.326679 ，在沒有print的情況下竟然用了1分多鐘，並且數字越大計算越慢。這樣的效率肯定是不被允許的。下面介紹一種最常見的質數演算法的原理：

三、埃拉托色尼素數篩選法

埃拉托色尼是一名古希臘的地理學家，他是世界上第一個計算出地球周長的人。埃拉托色尼素數篩選法可以很快速的計算出1到N之間的所有素數。將n開根號，即N^0.5，去掉2到N^0.5中所有素數的倍數，剩下的數便都是素數了。例如求1到25中的素數有哪些，第一步是將25開根號，得到5；第二步將2到5的素數取出來，分別是2、3、5；再將2到25中且是2、3、5的倍數的數去掉，即去掉4、6、8、9、10、12、14、15、16、18、20、21、22、24、25，剩下2、3、5、7、11、13、17、19便是1到25中的所有素數了。

這裡還用到了一個數學知識，即只要小於或等於根號N的數（1除外）不能整除N，則N一定是素數；反過來說就是只要小於或等於根號N的數（1除外）能整除N，則N一定是合數。下面給出證明過程：

假設一個數N是合適，那一定存在一個因數b和一個非1且非自身的因數a，即a*b=N

等式兩邊同時開根號得出：(a*b)^0.5=a^0.5*b^0.5=N^0.5

可以推出：若N為合數，則a和b中一定有一個大於或等於N^0.5，另一個小於或等於N^0.5

按照這個結論，就只需計算小於等於N^0.5的數了，這樣就大大提高了效率（要注意等於N^0.5的這個邊界）：

#求10萬以內的素數
import datetime
start = datetime.datetime.now()
for i in range(2,100000):
for j in range(2,int(i**0.5+1)): #邊界需要加1
if i%j == 0:
break
#else:
#print(i)
stop = datetime.datetime.now()
print(stop-start)

運行結果： 0:00:00.428024 。可以說是質的飛躍。

小的優化

我們也可以將偶數事先就排除在外，然後在進行素數篩選：

#求10萬以內的素數
import datetime
start = datetime.datetime.now()
print(2)
for i in range(3,100000,2): #從3開始，跳過偶數
for j in range(2,int(i**0.5+1)):
if i%j == 0:
break
#else:
#print(i)
stop = datetime.datetime.now()
print(stop-start)

運行結果： 0:00:00.406024 ，又快了不少。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！