iT邦幫忙

5

寫程式實作Eratosthenes 篩法建質數表時,發現了質數在自然數中的密度趨近於0的證明

篩選出1~n的質數是程式的一道經典題目,
其中著名的算法稱為「埃拉托斯特尼篩法」,
可參考維基百科: 埃拉托斯特尼篩法的說明,
想法蠻簡單的,就是先建一張數字2~n的表格,

一開始,把2圈起來,標註質數,然後把2的倍數全刪了,
把3圈起來,標註質數,然後把3的倍數全刪了…
以此類推,附上可以做的題目來源及程式碼:

參考題目:

  1. LeetCode- 204. Count Primes- 計算小於n的質數有幾個
  2. CodeWar- Prime Streaming (PG-13)- 由小至大快速產生質數

參考程式碼: (python, 計算小於n的質數數量,用Eratosthenes 篩法)

import math

#find all primes less than n
def findPrime(n):
    if n<=2:
    	return []
    isPrime = [True]*n
    for i in range(3,int(math.sqrt(n))+1,2):
        if isPrime[i]:
            isPrime[i * i :: i] = [False]*len(isPrime[i * i :: i])
    return [2]+[i for i in range(3,n,2) if isPrime[i]]

質數占自然數多少比例思考

這時,我想到一個問題,
在篩質數的過程,
一開始把2的倍數刪掉,
相當於把自然數的1/2都去掉不會是質數
再來把3的倍數刪掉,
大約相當於把自然數的1/3都去掉不會是質數…

繼續下去,沒有被刪掉的比率大概是
1/2 * 2/3 * 4/5 * 6/7 * …

用數學式子來寫的話,
小於n的質數比例大概就是
https://ithelp.ithome.com.tw/upload/images/20200406/20117114S3Lowp1Lej.png

那麼… 如果把所有的質數(p-1)/p 相乘會趨近於0還是大於0的一個常數呢,
即(1/2 * 2/3 * 4/5 * 6/7 * 10/11 * 12/13 *…)一直乘會不會無限靠近於0?

動機: 從質數思考到宇宙

若你有耐心看到這裡,
你可能會想說學程式的人幹麻去思考這麼數學的問題?

我們把正整數「1,2,3,4,5,…」想成是整個無垠的宇宙好了,
質數在正整數中是特別的,可以把它想成是「有生命的行星」之類的

數學上,很早就證明出「質數有無限多個」,
彷彿是有人發現說宇宙裡面有無數個像地球一樣是有生命存在的行星那樣不可思議

但是儘管像地球一樣是有生命存在的行星有無數個,
但是可能有生命存在的地方在整個宇宙中的比例卻幾乎是0
(可能因此人類一直找不到外星生物)

這與跟等等要講的「質數有無限多個,但在自然數中的比例幾乎是0」一樣的不可思議,
給人一種既是無限,卻又很渺小的感覺

儘管宇宙中可能有無限多個像地球的行星,
但把全宇宙的地球加起來對宇宙來說又像不存在一樣,
何等奧妙?

數學式證明

天馬行空的想像結束了,
小馬剛好想起了之前在資工系學「高等離散結構」這門課時,學過一個數學公式:
https://ithelp.ithome.com.tw/upload/images/20200406/20117114yUUoJIKz2F.png

你大概很納悶為什麼讀資工系竟然還要上看起來這麼困難的數學課,
小馬也非常的納悶,
或許是因為數學學的好的人打程式的邏輯通常也會很好所以值得學?

更神奇的是,
這個數學式竟然有一天小馬還剛好想到可以拿來用
這個式子的證明其實也不會到很難(跟困難的微積分相比),
大概兩頁投影片證完:
https://ithelp.ithome.com.tw/upload/images/20200406/20117114fcrn505Uzt.png
https://ithelp.ithome.com.tw/upload/images/20200406/20117114emzMyIvuqQ.png

如果把s=1代入這個式子的話,
恰好會發現就得到我們原本想算的所有的質數(p-1)/p 相乘的式子
https://ithelp.ithome.com.tw/upload/images/20200406/20117114hc4Ga9x9w6.png

在數學上 (by wiki調和級數),

1+1/2+1/3+…+1/n 大約就是 ln n

所以結論就是當n趨近於無限大時,
所有小於n的質數的比例大約是(1/ln n)

把所有的質數(p-1)/p 相乘會趨近於0,
即(1/2 * 2/3 * 4/5 * 6/7 * 10/11 * 12/13 *…)一直乘會無限靠近於0,
也就有質數在整個自然數中的密度趨近於0的結論了

(補充: 事後在wiki- 質數定理看到小於n的質數的比例真的大約是(1/ln n),沒想到寫程式恰巧想到了這個結論)


尚未有邦友留言

立即登入留言