Count Primes

问题:

找出不大于非负整数n的所有素数的个数

解答:
思路     先去掉偶数(n/2, 不包括2但包括1),然后从i=3开始的奇数进行扫描(以j=i*i为起点,step = 2*i为步长进行扫描)

class Solution {
public:
    int countPrimes(int n) {
        if(n <=2)
            return 0;
        int res = n>>1, m = sqrt(n-1);    // initilize res to n/2, remove all even number(not 2) and 1
        bool *table = new bool[n];
        for(int i = 3; i <= m; i +=2){
            if(!table[i]){                // odd prime
                for(int step = i<<1, j = i*i; j < n; j += step){   // start from i*i, step 2*i
                    if(!table[j]){
                        table[j] = 1;
                        res--;
                    }
                }
            }
        }
        return res;
    }
};

 

Leave a Reply

Your email address will not be published. Required fields are marked *