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

一種快速找到素數的方法

發布時間: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函數中,僅是對數函數的積分,而對數函數只是指數函數的反函數也。

閱讀全文

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

熱點內容
蘋果手機有別的方法找序列號嗎 瀏覽:241
自製書簽的方法及圖片卡通 瀏覽:790
30乘以25的簡便方法 瀏覽:526
鋪床的方法圖片 瀏覽:167
乾薑功效與作用及食用方法 瀏覽:469
防止衣服掉毛的方法有哪些 瀏覽:282
腳弓傳球訓練方法有哪些 瀏覽:755
十二指腸球部潰瘍的治療方法 瀏覽:409
陰道炎治療方法 瀏覽:314
火龍快速長大方法 瀏覽:165
分析化學計算題方法 瀏覽:696
晚上拔掉手機正確方法 瀏覽:569
魯b車牌安裝方法 瀏覽:570
有哪些方法把煙戒掉 瀏覽:710
保養五臟的簡單有效的鍛煉方法 瀏覽:518
夾箭君子蘭最佳治療方法 瀏覽:310
鹿茸片的用處及食用方法 瀏覽:402
可使用的檢測校準方法 瀏覽:308
簡單快速解酒方法 瀏覽:6
電話正確使用方法視頻 瀏覽:870