C++ 解法, 执行用时: 4ms, 内存消耗: 416KB, 提交时间: 2022-06-23

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int primesCount(int n) {
        if(n==1) return 0;
        if(n==2) return 1;
        vector<bool> isPrime(n+1,true);
        for(int i=2;i*i<n;++i){
            if(isPrime[i]){
                for(int j=2*i;j<n;j+=i){
                    isPrime[j] =false;
                }
            }
        }
       int  count =0;
        for(int i=2;i<n;++i){
            if(isPrime[i]) count++;
        }
        return count;
    }
    
};

C++ 解法, 执行用时: 4ms, 内存消耗: 420KB, 提交时间: 2022-07-10

class Solution {
  public:
    int primesCount(int n) {
        if (n == 1) return 0;
        if (n == 2) return 1;        
        vector<bool> v(n + 1, true);
        for (int i = 2; i * i < n; ++i) {
            if (v[i]) {
                for (int j = 2 * i; j < n; j += i) {
                    v[j] = false;
                }
            }
        }       
        int c = 0;
        for (int i = 2; i < n; ++i) {
            if (v[i]) c++;
        }
        return c;
    }

};

C++ 解法, 执行用时: 4ms, 内存消耗: 440KB, 提交时间: 2022-05-30

class Solution {
public:
    int primesCount(int n) {
        if (n <= 1) return 0;

        isPrime.assign(n, true);
        isPrime[0] = isPrime[1] = false;

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

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

private:
    vector<bool> isPrime;
};

C++ 解法, 执行用时: 4ms, 内存消耗: 484KB, 提交时间: 2022-06-22

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int primesCount(int n) {
        // write code here
        // 筛选法
        vector<bool> flag(n);
        int res = 0;
        for (int i = 2; i < n; i ++ ) {
            if (!flag[i]) {
                res ++;
                for (int j = i + i; j < n; j += i) flag[j] = true;
            }
        }
        return res;
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 516KB, 提交时间: 2022-07-27

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int primesCount(int n) {
        // write code here
      vector<bool> st(n + 1);
      vector<int> primes;
      
      for (int i = 2; i < n; i ++)
      {
        if(!st[i]) primes.push_back(i);
        for (int j = 0; primes[j] * i <= n; j ++)
        {
          st[primes[j] * i] = true;
          if(i % primes[j] == 0) break;
        }
      }
      return primes.size();
    }
};