質數又稱素數。指整數在一個大于1的自然數中，除了1和此整數自身外，沒法被其他自然數整除的數。換句話說，只有兩個正因數（1和自己）的自然數即為素數。比1大但不是素數的數稱為合數。1和0既非素數也非合數。素數在數論中有著很重要的作用。
質數的分布規律是以36N（N+1）為單位，隨著N的增大，素數的個數以波浪形式漸漸增多。
孿生質數也有相同的分布規律。
素數，普遍認為的分布規律是沒有規律。時而連續出現，時而又相隔很遠很遠。有遠親、有近鄰，地球對面也還有幾個好朋友。
素數,真的就沒有規律嗎？
合數可以用公式來表示，而素數且不能用公式來表示。這就是素數。
不過這里其實就蘊含著秘密。
既然合數能用公式表示，間接的也就說明了，素數必須服從這些公式的限制。而研究合數，其實也是研究素數。
有2個根深蒂固的觀念：
1、素數的個數總是按照自然數增加10倍來統計展現的。因為這里一直沿用π(x)與x/lnx的統計方法。
2、100以內有25個素數，1000以內有168個素數。就產生了一種根深蒂固的觀念：素數越來越稀疏。
當然這些都沒有錯誤，否則也不會一直陪伴著素數研究到現在，但它禁錮了人們的思想。有一些數據似乎與之相悖。
列舉一些四胞胎素數的例子，
四胞胎素數是很少的，在自然數1000億以內僅僅有1209317組。平均間距為82691。兩組之間相距是很遠的。但總有一些間距僅僅為30的兩對四胞胎素數稀稀拉拉的出現。在1000億以內共有這樣四胞胎素數267對，他們是如何分布的呢？
200億以內有90個；200-400億之間有55個；
剩下的如何分布的呢，你不會相信的：
400-600億之間有41個；
600-800億之間有41個；
800-1000億之間有40個；
這樣的分布說明了什么？均勻分布？大家肯定不會相信的，我也不信，那似乎就只能是巧合了。大家一定也會認為是這純屬巧合。素數嘛，飄忽不定，怎么分布都有可能，但就是沒有規律。至少大家還沒有發現其分布規律。
count = 0
for i in range(2,101):
for x in range(2,i):
if i%x == 0:
break
else:
print(i)
count += 1
print("\n","Total: ",count,"number")
----
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
Total: 25 number這種方法的思路，時間復雜度是O(n2)，2層循環，雖然會break，但效率還是很低的
其實我們發現我們求解質數的時候，根本不需要從2除到N-1，當除數大于商的時候我們就不用計算了。
用數學的話來說我們只需除到平方根就好了
count = 0
for i in range(2,100000):
for x in range(2,int(i**0.5)+1):
if i%x == 0:
break
else:
print(i)
count += 1
print("\n","Total: ",count,"number")
----
2
3
5
7
11
13
·······
99907
99923
99929
99961
99971
99989
99991
Total: 9592 number所以對于偶數都不用判斷是不是素數，修改步長
count = 1
print(2)
for i in range(3,100000,2):
for x in range(2,int(i**0.5)+1):
if i%x == 0:
break
else:
print(i)
count += 1
print("\n","Total: ",count,"number")
----
2
3
5
7
11
13
·······
99907
99923
99929
99961
99971
99989
99991
Total: 9592 number第二層for循環判斷的是奇數/range(2，奇數的開方)
但是2,4,6,8···這種數肯定不能被奇數整除，不用考慮，可以不加判斷
count = 1
print(2)
for i in range(3,100000,2):
for x in range(3,int(i**0.5)+1,2):
if i%x == 0:
break
else:
print(i)
count += 1
print("\n","Total: ",count,"number")
----
2
3
5
7
11
13
·······
99907
99923
99929
99961
99971
99989
99991
Total: 9592 number計算以上的程序運行時間，取1000000以內的質數
from datetime import datetime
t1 = datetime.now()
count = 0
for i in range(2,1000000):
for x in range(2,i):
if i%x == 0:
break
else:
#print(i)
count += 1
print("\n","Total: ",count,"number")
t2 = datetime.now()
print("Total_Cost:",(t2-t1).total_seconds(),"s")我喝了一杯咖啡，還沒計算完...已經超過五分鐘了，不等了
然后減少10倍，測試100000以內的數據...用了40s
from datetime import datetime
t1 = datetime.now()
count = 0
for i in range(2,1000000):
for x in range(2,int(i**0.5)+1):
if i%x == 0:
break
else:
#print(i)
count += 1
print("\n","Total: ",count,"number")
t2 = datetime.now()
print("Total_Cost:",(t2-t1).total_seconds(),"s")
----
Total: 78498 number
Total_Cost: 6.26467 s用了6.26467s,效率大大提升
from datetime import datetime
t1 = datetime.now()
count = 1
#print(2)
for i in range(3,1000000,2):
for x in range(2,int(i**0.5)+1):
if i%x == 0:
break
else:
# print(i)
count += 1
print("\n","Total: ",count,"number")
t2 = datetime.now()
print("Total_Cost:",(t2-t1).total_seconds(),"s")
----
Total: 78498 number
Total_Cost: 5.80345 s用了5.80345s,效率稍微進步
from datetime import datetime
t1 = datetime.now()
count = 1
#print(2)
for i in range(3,1000000,2):
for x in range(3,int(i**0.5)+1,2):
if i%x == 0:
break
else:
#print(i)
count += 1
print("\n","Total: ",count,"number")
t2 = datetime.now()
print("Total_Cost:",(t2-t1).total_seconds(),"s")
----
Total: 78498 number
Total_Cost: 3.375002 s用了3.375002s,效率約提高50%
from datetime import datetime
t1 = datetime.now()
count = 1
lst = [2]
for i in range(3,1000000,2):
#for x in range(3,int(i**0.5)+1,2):
for x in lst:
if i%x == 0 and x <= i**0.5:
break
else:
lst.append(i)
count += 1
t2 = datetime.now()
print("Total Number:", count, "Total_Cost:", (t2-t1).total_seconds(),"s")
----
Total Number: 78498 Total_Cost: 234.643142 s因為每次都要if判斷兩次結構（a and b）,效率會低，修改下方案
from datetime import datetime
t1 = datetime.now()
count = 1
lst = [2]
for i in range(3,1000000,2):
flag = False
middle = int(i**0.5)
for x in lst:
if i%x == 0:
break
if x > middle:
flag = True
break
if flag:
lst.append(i)
count += 1
t2 = datetime.now()
print("Total Number:", count, "Total_Cost:", (t2-t1).total_seconds(),"s")
----
Total Number: 78498 Total_Cost: 1.560107 s可以可以，上面的方法四計算1000000內素數用時是3.37s，而現在，只需要1.56s,效率又提高50%以上
有一個數在做無用功，它就是2，任何素數都不能整除2
from datetime import datetime
t1 = datetime.now()
count = 2 #[2]
lst = [3]
for i in range(5,1000000,2):
flag = False
middle = int(i**0.5)
for x in lst:
if i%x == 0:
break
if x > middle:
flag = True
break
if flag:
lst.append(i)
count += 1
t2 = datetime.now()
print("Total Number:", count, "Total_Cost:", (t2-t1).total_seconds(),"s")
----
Total Number: 78498 Total_Cost: 1.513069 s略微提升，也有效果
還有嗎？
在求無限質數的時候，我們不能預測有多少結果
但是對于求1000000內質數，我們現在知道了有多少結果
這樣就可以提前開辟內存空間，替代append()
還有別的方法嗎？當然有！孿生素數了解下
孿生素數就是指相差2的素數對，例如3和5，5和7，11和13…。孿生素數猜想正式由希爾伯特在1900年國際數學家大會的報告上第8個問題中提出，可以這樣描述：存在無窮多個素數p，使得p + 2是素數。素數對（p, p + 2）稱為孿生素數。
總結下來就是一句話：當素數大于3時，素數都在 6N-1 和 6N+1 左右分布
| 素數 | 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | 25 |
|---|---|---|---|---|---|---|---|---|---|---|
| 步長 | 2 | 4 | 2 | 4 | 2 | 4 | 2 | 4 |
由此，在循環中用一個可變步長就可以，C語言有可變步長;
然而Python沒有可變步長這一說- -
下面上代碼實現
from datetime import datetime
t1 = datetime.now()
count = 3 #2,3,5
lst = [3,5]
step = 4
i = 7
while i < 1000000:
if i%5 != 0:
middle = int(i**0.5)
flag = False
for x in lst:
if i%x == 0:
break
if x > middle:
flag = True
break
if flag:
lst.append(i)
count += 1
i += step
step = 4 if step == 2 else 2
t2 = datetime.now()
print("Total Number:", count, "Total_Cost:", (t2-t1).total_seconds(),"s")
----
Total Number: 78498 Total_Cost: 1.35155 s1.513069s —> 1.35155s 還可以哈哈
量子計算機，了解一下......密碼學、區塊鏈都將被重新定義~
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
