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

一種快速找到素數的方法

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

閱讀全文

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

熱點內容
提供肌肉燃料的最佳方法 瀏覽:821
區域創新能力評價研究用什麼方法 瀏覽:628
美利達真偽鑒別方法 瀏覽:71
腳趾頭關節炎的治療方法 瀏覽:294
歐萊雅潤發乳使用方法 瀏覽:459
剁椒蝦怎麼做製作方法 瀏覽:284
旋轉樓梯安裝玻璃施工方法 瀏覽:730
舒緩的口腔潰瘍最快解決方法 瀏覽:326
孩子不健康用什麼方法引產 瀏覽:60
水療素的使用方法 瀏覽:275
會陰疝治療方法 瀏覽:834
抗肝炎的治療方法 瀏覽:829
豆腐乳的正確清洗方法 瀏覽:746
你知道哪些種子旅行的方法嗎 瀏覽:477
斷橋鋁推拉窗戶的安裝方法 瀏覽:308
工程斷橋窗戶安裝方法 瀏覽:627
快速自我鼓勵方法 瀏覽:376
貴陽戀愛挽回方法有哪些 瀏覽:942
幼兒園研究棋類的方法 瀏覽:268
腳丫子撞疼用什麼方法去痛 瀏覽:835