LeetCode-204. Count Primes [C++][Java]

LeetCode-204. Count PrimesLevel up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.https://leetcode.com/problems/count-primes/

Given an integer n, return the number of prime numbers that are strictly less than n.

Example 1:

Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Example 2:

Input: n = 0
Output: 0

Example 3:

Input: n = 1
Output: 0

Constraints:

0 <= n <= 5 * 106

【C++】

埃拉托斯特尼筛法_百度百科埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。https://baike.baidu.com/item/%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%E7%89%B9%E5%B0%BC%E7%AD%9B%E6%B3%95/374984?fr=aladdin

class Solution {
public:
    int countPrimes(int n) {
        if(n <= 1) return 0;
        bool isPrime[n];
        for(int i=2; i 
2. 优化重复 
class Solution {
public:
    int countPrimes(int n) {
        if (n <= 2) {return 0;}
        vector prime(n, true);
        int i = 3, sqrtn = sqrt(n), count = n / 2; // 偶数一定不是质数
        while (i <= sqrtn) { // 最小质因子一定小于等于开方数
            for (int j = i * i; j < n; j += 2 * i) { // 避免偶数和重复遍历
                if (prime[j]) {
                    --count;
                    prime[j] = false;
                }
            }
            do {i += 2;} while (i <= sqrtn && !prime[i]); // 避免偶数和重复遍历
        }
        return count;
    }
};
 
 
【Java】 
class Solution {
    public int countPrimes(int n) {
        if(n <= 1) return 0;
        boolean[] isPrime = new boolean[n];
        for(int i=2; i