Description:

    Count the number of prime numbers less than a non-negative number, n.

    計算小于n的非負整數(shù)中素數(shù)的個數(shù)，

LeetCode204:Count Primes

。

    素數(shù)又稱質數(shù)，是指只能被1和它自身相除的自然數(shù)。需要注意的是1既不是素數(shù)也不是合數(shù)。2是最小的素數(shù)。

    使用判斷一個數(shù)是否是素數(shù)的函數(shù)，那么這個函數(shù)需要進行一輪循環(huán)，在給定的小于n中又要進行一輪循環(huán)。所以時間復雜度是O(n^2)。

    可以對判斷一個數(shù)是否是素數(shù)的函數(shù)進行優(yōu)化，對于數(shù)i，可以只對2到√i之間的數(shù)進行判斷，這樣時間復雜度降低到了O(nlogn)。

    但是上面的解法在leetcode中還是超時。

    于是想是否存在只進行一輪循環(huán)的方法，即在遍歷1至n-1一次的過程中記錄下素數(shù)的個數(shù)，但是后面就不知道怎么處理。

    然后看leetcode中的小提示,發(fā)現(xiàn)了一種更優(yōu)的尋找素數(shù)的方法。首先看下面的這個圖：

   

    這個圖其實就道出了這個算法是怎么進行的。使用一個長度是n的hash表，最開始這個hash表中的所有元素都是沒有被處理的，從2開始遍歷，如果這個元素沒有被處理，那么將素數(shù)的個數(shù)加1，然后將2*2,2*3,2*4……2* k（ 2* k < n）標記為已經(jīng)被處理了的。接著開始處理3，同理將3*2,3*3,3*4…..3*m( 3 * m < n)標記為已被處理了的，接著是4，由于這個元素已經(jīng)被處理，繼續(xù)向后遍歷，這樣一直處理下去，

電腦資料

《LeetCode204:Count Primes》(http://www.msguai.com)。<喎?http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPrTT1eK1wMzi1tDT1tLiyra1vcHL0ru49tX7yv274dLns/a74bW81sLOyszitcTQoby8x8mhozwvcD4NCjxwPsG91ta94reot9ax8Mjnz8KjujwvcD4NCjxwcmUgY2xhc3M9"brush:java;">class Solution {public:/*//解法一：超時 int countPrimes(int n) { int count=0; for(int i=2;i<=n;i++) { if(isPrime(i)) count++; } return count; } bool isPrime(int n) { if(n==1) return false; for(int i=2;i*i<=n;i++) { if(n%i==0) return false; } return true; } *///解法二： int countPrimes(int n) { int * mask=new int[n]();//可以在這里直接對動態(tài)數(shù)組進行初始化 int count=0; for(int i=2;i