204. Count Primes - cocoder39/coco39_LC GitHub Wiki

204. Count Primes

start from 2, get each number's multiples, which is guaranteed to be non-prime. 2 : 4, 6, 8, 10... 3 : 6, 9, 12, ... 5 : 10, 15, ...

optimizations:

• for (int i = 2; i * i <= n; i++). we only check multiples of range from 2 to i where i^2 <= n, reduce duplicate calculation. (eg,. if we have found out that 12 = 2 * 6 is not a prime, we don't need check if 12 is 6's multiples since 6 > 12 ^ 0.5)
• if (! isPrime[i]). get each prime's multiples, which is guaranteed to be non-prime. Non-prime generated from prime, its multiples are also prime's multiples.
• for (j = i * i; j <= n; j += i). when we check 5' multiples, we only check 5 * 5 and greater, 5 * 2, 5 * 3.. should have been checked.

time is O(n log log n)

int countPrimes(int n) {
        vector<bool> isPrime(n + 1, true);
        for (int i = 2; i * i <= n; i++) {
            if (! isPrime[i]) {
                continue;
            }
            for (j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
        
        int res = 0;
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                res++;
            }
        }
        return res;
    }