Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 204. Count Primes

---

題目：


解答：

class Solution {
public:
    int countPrimes(int n) {
        if (n <= 2) {
            return 0;
        }

        vector<int> prime(n, 1);

        prime[0] = 0;
        prime[1] = 0;

        for (int i = 2; i * i < n; ++i) {
            if (prime[i]) {
                for (int j = i * i; j < n; j+= i) {
                    prime[j] = 0;
                }
            }
        }

        int ans = 0;
        for (int i = 2; i < n; ++i) {
            ans += prime[i];
        }

        return ans;
    }
};