[LeetCode]204. Count Primes

题目描述

思路

类似动态规划，每次计算当前素数时，将不可能是素数的结果标记，之后遍历碰到这些结果直接跳过

代码

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int countPrimes(int n) {
        if (n <= 2) return 0;
        vector<int> passed(n, 0);

        int sum = 1, upper = sqrt(n);
        for (int i = 3; i < n; i += 2) {
            if (!passed[i]) ++sum;
            if (i > upper) continue;
            for (int j = i * i; j < n; j += i) passed[j] = 1;
        }

        return sum;
    }
};


int main() {
    Solution s;

    cout << s.countPrimes(2) << endl;
    cout << s.countPrimes(3) << endl;
    cout << s.countPrimes(4) << endl;
    cout << s.countPrimes(6) << endl;

    system("pause");
    return 0;
}