?

題目標(biāo)簽

HashTab（哈希表）

?

題意及思路

題意：略

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

?

轉(zhuǎn)載于:https://www.cnblogs.com/kyrie211/p/11211950.html

總結(jié)

以上是生活随笔為你收集整理的LeetCode -- 204. Count Primes的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。