LeetCode: 204. Count Primes

题目描述

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

Example:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

解题思路

首先统计素数表，然后统计素数 表中的内容。

AC 代码

class Solution 
{
public:
    int countPrimes(int n)
    {
        vector<bool> isPrime(n, true);
        isPrime[0] = false;
        isPrime[1] = false;
        isPrime[2] = true;
        
        // 标记非素数
        for(int i = 2; i < n; ++i)
        {
            if(isPrime[i] == false) continue;
            
            int notPrime = i*2;
            while(notPrime < n)
            {
                isPrime[notPrime] = false;
                notPrime += i;
            }
        }
        
        // 统计素数的数量
        int cnt = 0;
        for(int i = 0; i < n; ++i)
        {
            cnt += isPrime[i];
        }
        
        return cnt;
    }
};