Eratosthenes sieve c程序 - 爲什麼我們有<= sqrt（n）等？

我想這更像是一個數學問題，但它與編程有很大關係，所以我想我會試一試。下面是我的代碼使用埃拉托色尼的篩程序鏈接在C計算質數的列表：在節目的開頭Eratosthenes sieve c程序 - 爲什麼我們有<= sqrt（n）等？

我的問題是，在for循環，爲什麼我們有i < = sqrt（n）和j < = n/j？這是我的教授建議的，它適用於程序的目的（不超過數組的內存限制等），但我不完全理解它爲什麼起作用。

謝謝！

2012-02-14 Joshpho

我<= SQRT（n）是由於因素之一必須低於或等於所述數目的平方根以許多 – Treesrule14 2012-02-14 06:04:00

的任何因式分解'我<= sqrt（n）'是一個非常緩慢的操作，並涉及與浮點無關的操作中的浮點操作。相反，你應該把表達式寫成'i * i <= n'。 – 2012-02-14 06:07:31

注意，如果你已經知道'i * i'的值，'（i + 1）*（i + 1）'的值很容易計算爲'i * i + 2 * i + 1'（沒有任何乘法）。 – 2012-02-14 06:09:04

要麼n = a * a，或n = b * c，其中b < a < c。因此，我們只需要檢查值高達a - 達到a * a的平方根 - 以找到a或b。如果我們找到b，那麼我們知道c（如c = n/b）。

2012-02-14 06:14:27

如果一個數字（命名爲NUM）NUM> SQRT（n）和是不是素數
NUM必須是：NUM = A * B的
一個和B必須低於SQRT（n）的
所以它的數量開方以下步驟（N）
所以沒有必要過度開方判斷數（n）
你可以寫這樣的代碼

之前就已經削弱

for(j = 2 ; i * j <= n ; j++) 
{ 
    primecap[j * i] = FALSE; 
}

那麼它必須是更容易理解

2012-02-14 08:12:09 fork123x

回答