LeetCode -- 204. Count Primes

?

題目標簽

HashTab（哈希表）

?

題意及思路

題意：略

思路：有關素數的題目我所知道有兩種做法。一種是最基本的isPrime算法，關鍵點在循環判斷時，上限為Math.sqrt(n) （求n是否為素數）。另外一種做法是，求某段區間內的素數個數，一般比賽中，n一般很大，這時候一般會采用素數表（Table），素數表的求法是，先記2到n的數為1（或true，意味著是素數），然后進行循環，對每個i來說，其倍數的數必定不是素數，將其置為0（或false）。當然你一開始置所有的數都為0，總體思路如此。

?

代碼

class Solution {public int countPrimes(int n) {int primeTable[] = new int[n];for(int i=2;i<n;i++){primeTable[i] = 1;}for(int i=2;i*i<n;i++){
　　　　　　　if(primeTable[i]==0) continue;for(int j=i*i;j<n;j+=i){primeTable[j] = 0;}}int ans = 0;for(int i=0;i<n;i++){if(primeTable[i]==1) ans++;}return ans;}
}    

?