原始數

衆所周知，要檢查數字「n」是否爲素數，我們只需檢查它是否具有小於n的平方根的因數。原始數

我的問題是不是檢查小於n的平方根的所有素數就足夠了。

來源

2017-02-25 Anurag Jain

是的，如果你碰巧知道素數。 – JJJ

小於或等於...否則你會認爲例如。 4和9是素數。 –

我投票結束這個問題，因爲它不是關於編程。 –

我們可以說這樣的：

讓數以檢查是n。假設有一個k <= sqrt(n)，它除以n。現在，我們可以寫k如下：

k = (p_1^a_1)(p_2^a_2)...(p_x^a_x)

其中p_1, p_2, ..., p_x是質數小於或等於k和a_1, a_2, ..., a_x >= 1。現在，由於k除以n，並且由於我們知道p_1, p_2, ..., p_x除k，通過傳遞性，我們可以推斷出p_1, p_2, ..., p_x除n。因此，爲了證明n是非素數，檢查是否有任何素數<= sqrt(n)除以n就足夠了。

來源

2017-02-25 11:02:45 Shubham

Upvoted，但你的論點可以更簡單 - k至少有一個素因子p，p | k | n，所以p除以n。 [當n是素數的平方時，您還需要檢查素數<= sqrt（n）而不是

@PaulHankin感謝您指出最後一個參數中缺少的'equals'。我同意我的論點有點冗長，但我認爲論證（你的和我的）的外殼是一樣的。我應該修剪我的答案嗎？ – Shubham

是的，我同意這是一個想法。我認爲如果你將它編輯下來，它會更好的回答，因爲這會讓這個想法更容易被看到。但如果你想這樣做，取決於你。 –

每個整數n大於1或者是素數本身或者是素數（Fundamental theorem of arithmetic）的乘積。因此，如果n本身不是主要的，它必須能被至少兩個素數整除。這些中的至少一個必須小於或等於√Ñ（否則他們的產品將是大於Ñ），因此它是足夠的，以檢查所有的素數小於或等於√n。

來源

2017-02-25 15:46:32

是的，你所說的絕對正確。

您只需要檢查所有小於squareRoot(n)的素數，但問題是您不知道數字是否爲素數。所以，你遍歷到squareRoot(n)

來源

2017-02-25 16:10:20

是的，它只是需要檢查的因素少sqrt（n）。但是這個算法有點慢。我還有一個更好的算法稱爲Miller_Rabin_primality My previous project code Source code

這裏是Wiki

來源

2017-02-27 20:43:16

回答

相關問題