# 204. Count Primes

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

### 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

Hide Similar Problems

```//思路首先：一个数不是合数就是素数，合数更好判断呢！
//合数：任何一个合数都可以表现为适当个素数的乘积的形式，
//所以我们只用小于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;//用于存储素数
};```