關鍵字

計算數論: 時間復雜度 空間復雜度 質數 合數 sieve of eratosthenes ,質數定理 條件概率 貝葉斯理論

睡夢——>昨晚:

昨晚由于某些原因失控了，做了一些此刻我認為不該做的事情。但，有一點我沒做了:玩王者榮耀。以前的時候，遇到這種導致"失眠"的情況，我會選擇王者榮耀來讓自己冷卻。這一點，值得我深化:不要再以任何借口去玩王者榮耀，它對我來說就是毒品。

昨日回顧:

LEARN:

刻意訓練難點， 組塊化圖書館構建復雜知識體系，神經遞質決定了我們做事情的態度，交替學習讓不同知識組塊間交叉得以有創新的基礎。

SYNTAX Python3 :

輸出，語法:標識符，數據結構，操作符，變量

控制流:if while.for , 函數:5種參數

模塊

今日回顧:

計算數論:

時間復雜度 空間復雜度

考慮時間(運行布數)和空間(存儲)隨著數據的增大或者增多所帶來的變化。

時間復雜度大致有以下:

O(n) = 1, lnx, x xlnx , x^2, x^3....

質數 合數

質數(prime):

任何大于1的整數，如果只能被1和它自身整除，則為質數(素數)，換句話說，除了1和它自身，質數無其他因數。

簡單質數如下:2 3 5 7 11.....質數有無限個。

除2以外，質數都是奇數。——> 除2以外，偶數都不是質數。

除2和3以外，其他所有的質數都滿足 6k+1,6k-1 (或者6k+5)，且k>1，k為整數。

合數(composite)

對于大于一的正整數，不是質數就是合數。

合數至少有四個因數。

任何合數都能被分解為多個質數相乘。

合數=質數x質數x質數

質數判定

對于一個給定的正整數N，如何判定其為質數(合數)？

2到Root(N)區間，不存在任何一個整數能整除N，則N為質數(更容易理解:在這個區間，只要存在一個整數能整除N，則N為合數)

偽代碼(以下Root(N) 表示N的平方根):

Def is_Prime(N):

flag = 0

For num from 2 to Root(N):

IF num能整除N

flag = 1

break

IF flag = 0

print N為質數

Else

print N為合數

總結一下存在任何一個 就成立 與 不存在任何一個才成立的代碼思路:

flag = 0

for 循環

if conditionTrue

flag = 1

break

if flag = 0

print 不存在任何一個元素符合循環條件

else

print 只要有一個元素符合循環條件

考慮到時間復雜度，優化:

3到Root(N)區間，沒有任何一個奇數能整除N，則N為質數:

Def is_Prime(N):

flag=0

For num from 2 to Root(N), step=2 :

IF num能整除N

flag=1

break

IF flag=0

printN為質數

Else

print N為合數

具體實現請點擊

sieveoferatosthenes:

埃拉托斯特尼篩 :

一個簡單的篩選100以內素數的方法:

畫一個10*10表格，去掉1

去除2的倍數

所有的偶數都不是質數/素數，所以去掉2的倍數(另一個角度是2的倍數2N 可由除1與2N外的其他質數相乘而得)

去除3的倍數，同2

去除5的倍數，7的倍數

剩余的數便是所有100以內的質數

-(補充:判斷一個數是不是質數，100為例

) 判斷整除范圍，100^(1/2)=10，from2to10(此處可以考慮兩個集合，①10作為分界點:10*10 ，若10左邊的某個數能整除100，則商一定在10的右邊。換句話說，判斷是否為質數轉化為判斷100是不是合數，而合數很容易判斷，只要100能被除了1與100的某一個數整除，就可以判定他是合數。根據①可知我只需要考慮2到10之間的數就可以。

更進一步，只需要考慮2到10之間的質數能否整除。)

其實以上去除倍數 可歸結為去除10( 為100的平方根 )以內所有質數的倍數

靈感:快速查找N^2 范圍內的所有質數

先做一個N*N的表格，去掉1

用類似的方法找到N以內的所有質數(根號N

根號N的表格 )

去除N以內所有質數的倍數，剩下的便是質數

應用:10以內的質數很容易記住:2 3 5 7

100以內的根據1010表格

10000以內的根據100100表格

偽代碼:

# 根據埃拉托斯特尼篩，篩選整數 n*n 以內的所有質數

List = range(n*n)

For num from 2 to n:

標記n*n以內所有num的倍數(2倍及2倍以上)為marked

unmarked便是所有的質數

質數密度曲線(需要再認真看一邊視頻)

質數數量(縱軸)——篩選空間N(橫軸)曲線:

當N越來越大，趨向于無窮大時，其曲線無限接近y=ln(x)的曲線

質數密度= 質數數量/篩選空間

1/ln(x)

質數定理

當N無窮大時，

條件概率

P(A|B)= P(AB)/P(B)

推導

P(AB)=P(A|B)/P(B)

P(BA)=P(B|A)/P(A)

因為

P(AB)=P(BA)=P(A∩B)

所以

P(A|B)/P(B)=P(B|A)/PA

所以P(A|B) / P(B|A) = P(A) /P(B)

P(A|B)條件概率:在 B發生的情況下，A發生的概率

P(AB) 聯合概率，A與B同時發生的概率

貝葉斯理論

總結

以上是生活随笔為你收集整理的可汉学院python_18-04-18 回顾 可汗学院:计算数论的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。