Python 中素?cái)?shù)的玩法

質(zhì)數(shù)

質(zhì)數(shù)又稱素?cái)?shù)。指整數(shù)在一個(gè)大于1的自然數(shù)中，除了1和此整數(shù)自身外，沒法被其他自然數(shù)整除的數(shù)。換句話說，只有兩個(gè)正因數(shù)（1和自己）的自然數(shù)即為素?cái)?shù)。比1大但不是素?cái)?shù)的數(shù)稱為合數(shù)。1和0既非素?cái)?shù)也非合數(shù)。素?cái)?shù)在數(shù)論中有著很重要的作用。
質(zhì)數(shù)的分布規(guī)律是以36N（N+1）為單位，隨著N的增大，素?cái)?shù)的個(gè)數(shù)以波浪形式漸漸增多。
孿生質(zhì)數(shù)也有相同的分布規(guī)律。

素?cái)?shù)，普遍認(rèn)為的分布規(guī)律是沒有規(guī)律。時(shí)而連續(xù)出現(xiàn)，時(shí)而又相隔很遠(yuǎn)很遠(yuǎn)。有遠(yuǎn)親、有近鄰，地球?qū)γ嬉策€有幾個(gè)好朋友。
素?cái)?shù),真的就沒有規(guī)律嗎？
合數(shù)可以用公式來表示，而素?cái)?shù)且不能用公式來表示。這就是素?cái)?shù)。
不過這里其實(shí)就蘊(yùn)含著秘密。
既然合數(shù)能用公式表示，間接的也就說明了，素?cái)?shù)必須服從這些公式的限制。而研究合數(shù)，其實(shí)也是研究素?cái)?shù)。
有2個(gè)根深蒂固的觀念：
1、素?cái)?shù)的個(gè)數(shù)總是按照自然數(shù)增加10倍來統(tǒng)計(jì)展現(xiàn)的。因?yàn)檫@里一直沿用π(x)與x/lnx的統(tǒng)計(jì)方法。
2、100以內(nèi)有25個(gè)素?cái)?shù)，1000以內(nèi)有168個(gè)素?cái)?shù)。就產(chǎn)生了一種根深蒂固的觀念：素?cái)?shù)越來越稀疏。
當(dāng)然這些都沒有錯(cuò)誤，否則也不會(huì)一直陪伴著素?cái)?shù)研究到現(xiàn)在，但它禁錮了人們的思想。有一些數(shù)據(jù)似乎與之相悖。
列舉一些四胞胎素?cái)?shù)的例子，
四胞胎素?cái)?shù)是很少的，在自然數(shù)1000億以內(nèi)僅僅有1209317組。平均間距為82691。兩組之間相距是很遠(yuǎn)的。但總有一些間距僅僅為30的兩對(duì)四胞胎素?cái)?shù)稀稀拉拉的出現(xiàn)。在1000億以內(nèi)共有這樣四胞胎素?cái)?shù)267對(duì)，他們是如何分布的呢？
200億以內(nèi)有90個(gè)；200-400億之間有55個(gè)；
剩下的如何分布的呢，你不會(huì)相信的：
400-600億之間有41個(gè)；
600-800億之間有41個(gè)；
800-1000億之間有40個(gè)；
這樣的分布說明了什么？均勻分布？大家肯定不會(huì)相信的，我也不信，那似乎就只能是巧合了。大家一定也會(huì)認(rèn)為是這純屬巧合。素?cái)?shù)嘛，飄忽不定，怎么分布都有可能，但就是沒有規(guī)律。至少大家還沒有發(fā)現(xiàn)其分布規(guī)律。

打印質(zhì)數(shù)

打印100以內(nèi)的質(zhì)數(shù)

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

這種方法的思路，時(shí)間復(fù)雜度是O(n2)，2層循環(huán)，雖然會(huì)break，但效率還是很低的

優(yōu)化算法，尋找中點(diǎn)

其實(shí)我們發(fā)現(xiàn)我們求解質(zhì)數(shù)的時(shí)候，根本不需要從2除到N-1，當(dāng)除數(shù)大于商的時(shí)候我們就不用計(jì)算了。
用數(shù)學(xué)的話來說我們只需除到平方根就好了

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

繼續(xù)優(yōu)化，大于2的偶數(shù)都不是質(zhì)數(shù)

所以對(duì)于偶數(shù)都不用判斷是不是素?cái)?shù)，修改步長(zhǎng)

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

進(jìn)行優(yōu)化，第二層的for循環(huán)

第二層for循環(huán)判斷的是奇數(shù)/range(2，奇數(shù)的開方)
但是2,4,6,8···這種數(shù)肯定不能被奇數(shù)整除，不用考慮，可以不加判斷

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

計(jì)算以上方法的效率

計(jì)算以上的程序運(yùn)行時(shí)間，取1000000以內(nèi)的質(zhì)數(shù)

方法一

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")

我喝了一杯咖啡，還沒計(jì)算完...已經(jīng)超過五分鐘了，不等了
然后減少10倍，測(cè)試100000以內(nèi)的數(shù)據(jù)...用了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,效率稍微進(jìn)步

方法四

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%

進(jìn)階方法

在上述方法四的基礎(chǔ)上，引入列表

先把第二層循環(huán)用列表替代

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

因?yàn)槊看味家猧f判斷兩次結(jié)構(gòu)（a and b）,效率會(huì)低，修改下方案

修改if and 結(jié)構(gòu)

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

可以可以，上面的方法四計(jì)算1000000內(nèi)素?cái)?shù)用時(shí)是3.37s，而現(xiàn)在，只需要1.56s,效率又提高50%以上

還能優(yōu)化嗎？

有一個(gè)數(shù)在做無用功，它就是2，任何素?cái)?shù)都不能整除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

略微提升，也有效果

還有嗎？

在求無限質(zhì)數(shù)的時(shí)候，我們不能預(yù)測(cè)有多少結(jié)果
但是對(duì)于求1000000內(nèi)質(zhì)數(shù)，我們現(xiàn)在知道了有多少結(jié)果
這樣就可以提前開辟內(nèi)存空間，替代append()

孿生素?cái)?shù)

還有別的方法嗎？當(dāng)然有！孿生素?cái)?shù)了解下

孿生素?cái)?shù)就是指相差2的素?cái)?shù)對(duì)，例如3和5，5和7，11和13…。孿生素?cái)?shù)猜想正式由希爾伯特在1900年國際數(shù)學(xué)家大會(huì)的報(bào)告上第8個(gè)問題中提出，可以這樣描述：存在無窮多個(gè)素?cái)?shù)p，使得p + 2是素?cái)?shù)。素?cái)?shù)對(duì)（p, p + 2）稱為孿生素?cái)?shù)。

總結(jié)下來就是一句話：當(dāng)素?cái)?shù)大于3時(shí)，素?cái)?shù)都在 6N-1 和 6N+1 左右分布

由此，在循環(huán)中用一個(gè)可變步長(zhǎng)就可以，C語言有可變步長(zhǎng);
然而Python沒有可變步長(zhǎng)這一說- -

下面上代碼實(shí)現(xiàn)

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 s

1.513069s —> 1.35155s 還可以哈哈

質(zhì)數(shù)相關(guān)的理論

• 哥德巴赫猜想：任何大于5的奇數(shù)都是三個(gè)素?cái)?shù)之和
• 衍生：任何一個(gè)大于2的偶數(shù)都是兩個(gè)素?cái)?shù)之和
• 伯特蘭猜想：對(duì)于任意正整數(shù)n>1，存在一個(gè)素?cái)?shù)p，使得n<p<2n
• 孿生素?cái)?shù)猜想：存在無窮多的形如p和p+2的素?cái)?shù)對(duì)
• n2+1 猜想：存在無窮多個(gè)形如n2+1的素?cái)?shù)，其中n是正整數(shù)

量子計(jì)算機(jī)，了解一下......密碼學(xué)、區(qū)塊鏈都將被重新定義~