204. Count Primes

Datetime:2016-08-23 01:21:58          Topic: LeetCode           Share

204. Count Primes

My Submissions

Total Accepted:  46354 Total Submissions:  204780 Difficulty:  Easy

Description:

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

Credits:

Special thanks to  @mithmatt for adding this problem and creating all test cases.

Subscribe to see which companies asked this question

Hide Tags
Hash Table   Math
//思路首先:一个数不是合数就是素数,合数更好判断呢!
//合数:任何一个合数都可以表现为适当个素数的乘积的形式,
//所以我们只用小于sqrt(number)的素数去除要判断的数即可,
//因为合数在sqrt(number)以内一定有素数的质因子
//比如要判断100以内的素数,只需判断合数即可,只用10以内的2,3,5,7就够了,10000以内的数用100以内的素数判断足以。
//运行时间O(N)
class Solution {
public:
    
    int countPrimes(int n) {
        if(n<=2)
            return 0;
        
        basenum.reserve(10001);//预留空间
        basenum.push_back(2);
       
        int cnt=1;
        for (int  number=3; number < n; number++)//计算出n以内的素数个数
        {
            int flag = true;
            int tmp = static_cast<int>(sqrt(number));
            //判断是否是素数
            int j = 0;
            while (basenum[j] <= tmp)
            {
                if (number % basenum[j] == 0)
                { //此时合数
                    flag = false; 
                    break; 
                }
                j++;
            }
            if (flag)
            { 
                basenum.push_back(number);
                cnt++;
            }
        }
        return cnt;
    }
private:
    vector<int> basenum;//用于存储素数
};




About List