|
上篇文章向大家介紹的判斷質(zhì)數(shù)是的方法，雖然可以很好的判斷一個數(shù)是否為素數(shù)。但是如果遇到了這樣的題，也難免會超時。 題目描述 輸出 2 - n 之間所有的素數(shù)。（包含 2 和 n ） 如果這種問題還采用一一判斷的話，時間復(fù)雜度顯然為O(N*N），如果時間限制是 1 s。當(dāng) N 大于 10000 就非常懸了，在加上一個 0 那就沒有懸念直接超時了。 這個時候我們就需要更精進的算法————素數(shù)表。 它的核心思想是，任何合數(shù)可以通過素數(shù)（或合數(shù)）的乘積表示，而素數(shù)都（除了1和自身）不可以。 說白了實現(xiàn)過程就是遇到素數(shù)就要把它的倍數(shù)記做合數(shù)，遇到合數(shù)跳過。首先默認(rèn)所有數(shù)為素數(shù)，0、1記做合數(shù)，從 2 開始遍歷，直到 n 。 0、1記做合數(shù)，從 2 開始遍歷， 2 是素數(shù)所以所有小于等于 20 的 2 的倍數(shù)（也就是除 2 以外的偶數(shù)）記做合數(shù)；3 是素數(shù)，所以 6，9，12， 15，18 都記做合數(shù)；4 是合數(shù)不管；5 是素數(shù)，所以10, 15, 20記做合數(shù)（20 在標(biāo)記 2 的倍數(shù)的時候就已經(jīng)記做合數(shù)了，不怕重復(fù)）；6不管；7是素數(shù)，14記做合數(shù)；8，9，10，12，14，15，16，18，20都是合數(shù)不管；11,13,17,19雖然都是素數(shù)，但是他們的倍數(shù)都大于20，故不用標(biāo)記。 說了這么多還是要用代碼實現(xiàn) |
|
|
