導航:首頁 > 方法技巧 > 一種快速找到素數的方法

一種快速找到素數的方法

發布時間:2022-11-30 13:56:27

A. 怎樣才可以快捷地判斷一個數是否是素數

對於素數這個概念,我們自然會想到這樣一個問題:怎樣從自然數集合中找出素數?素數到底有多少個?

假設給定一個自然數N,要求出N以內的所有素數,可以這樣進行:因為N以內的自然數只有三種,一種是1,一種是合數,一種是素數;我們可以象篩東西那樣,先把1篩掉,然後再把合數篩掉,剩下的就是素數了,這種在自然數列中尋找素數的方法就叫做埃拉托色尼篩法(簡稱埃氏篩法)。

用篩法找出不超過N的全部素數,可以遵循下面的定理進行。

輔助定理1:「如果n是不大於x的合數,那麼n必有一個不大於√x的素約數(符號「√」表示開平方)」(證從略)。根據輔助定理1,我們只要用不大於√x的素數作篩子,就可將不大於X以內的所有的合數篩除掉。

輔助定理2:「素數有無限多個」(證從略)。

雖然素數有無窮多個,但在自然數列中的一個相當長的數列中,卻找不到一個素數,而有時會出現若p是素數,p+2也是素數的情況,所以素數的出現並無規則可言。

一個素數只有1和本身這兩個約數,因此素數就不能再分解了。但是合數卻有兩個以上的素約數,那麼合數能不能分解成約數全部是素數的乘積呢?答案是肯定的。

唯一分解定理:「任何大於1的自然數都可以分解成素數的乘積,如果不計較這些素因數的順序,這種分解方法是唯一的」(證從略)。

根據唯一分解定理,欲求某自然數的倍數之數列,只要用該數乘以自然數列,即可得到該數的倍數之數列。由此可知,合數的出現是有規則可言的。埃氏篩法就是根據合數的出現是有規則可言的基礎上,逐個地將不大於√x的素數的倍數篩掉。根據輔助定理1,可知,篩掉那些具有不大於√x素約數的合數,序列中已無合數的存在,剩下的就是大於√x至x的素數了。

在運用篩法時,就可發現,當篩除某數的倍數時,有時會遇到數列中的數已被前一個篩子所篩,這樣就會造成計算上的誤差。針對此種情況,在數論有一個逐步淘汰原則:
「設有N件事物,其中,N_i件有性質i,N_j件有性質j, ..., N_ij件兼有性質i及j,...,N_ijk件兼有性質i、j及k,...。則此事物中之既無性質i,又無性質j,又無性質k,...者之件數為
N-N_i-N_j-N_k-...+N_ij+...-N_ijk-...+...-...。」①。

根據埃氏篩法和逐步淘汰原則,數論創建了求不大於X以內的素數之函數π(x)。所謂的π(x)函數,是指:
π(x)=N-r-1-{r∑i=1}[N/pi]+{∑1≤ii*pj]-...
+(-1)r[N/pi*pj*...*pr]
這是數論中求自然數列中素數的個數問題之唯一的一個根據規律而創建的函數,而所謂的素數定理中的Lix(x)函數僅是由於計算出來的數值有接近於π(x)函數中的數值而被高斯先生提議替代π(x)函數之用。因為在π(x)函數中的取整之步驟,使得計算成為十分繁瑣之事。但在Lix(x)函數中,並無所求素數的個數之任何規律,在Lix函數中,僅是對數函數的積分,而對數函數只是指數函數的反函數也。

閱讀全文

與一種快速找到素數的方法相關的資料

熱點內容
直流電壓的測量方法 瀏覽:477
小米5s藍牙哪裡設置方法 瀏覽:710
急迫性尿失禁的治療方法 瀏覽:353
如何遠離失眠的方法 瀏覽:134
黑頭棒使用方法 瀏覽:736
拼多多日發5000單的方法技巧 瀏覽:182
都保吸入劑使用方法 瀏覽:836
苦蕎麥喂牛的正確方法 瀏覽:829
足踝鍛煉方法圖片 瀏覽:923
古詩詞背誦方法研究 瀏覽:731
拆空調銅管的方法與步驟 瀏覽:308
從車內起步正確方法 瀏覽:90
沒想到這才是正確刷牙方法 瀏覽:100
機油量檢測正確方法 瀏覽:724
綠釉水盂瓷器鑒別的方法 瀏覽:376
羽毛快速摳出方法 瀏覽:183
spss常用的聚類分析方法 瀏覽:885
手機音效卡怎麼安裝使用方法 瀏覽:920
梳子線連接方法 瀏覽:672
手機泡水後發燙處理方法 瀏覽:50