题目标签

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;
    }
}