Count Primes

1. Description

2. Solution

• Version 1

代码语言：javascript复制

class Solution {
public:
    int countPrimes(int n) {
        if(n < 3) {
            return 0;
        }
        int count = 1;
        for(int i = 3; i < n; i  = 2) {
            if(isPrime(i)) {
                count  ;
            }
        }
        return count;
    }

private:
    bool isPrime(int n) {
        if(n < 2) {
            return false;
        }
        if(n == 2 || n == 3) {
            return true;
        }
        for(int i = 2; i * i <= n; i  ) {
            if(n % i == 0) {
                return false;
            }
        }
        return true;
    }
};

• Version 2

代码语言：javascript复制

class Solution {
public:
    int countPrimes(int n) {
        if(n <= 2) {
            return 0;
        }
        bool flag[n];
        int count = 1;
        memset(flag, true, sizeof(flag));
        for(int i = 2; i * i < n; i  ) {
            if(flag[i]) {
                for(int j = i * i; j < n; j  = i) {
                    flag[j] = false;
                }
            }
        }
        for(int i = 3; i < n; i  = 2) {
            if(flag[i]) {
                count  ;
            }
        }
        return count;
    }
};

version

0 人点赞