数据结构与算法面试题：给定非负整数 m 和 n，计算不大于 m 的数字中，素数的个数。（提示：算法原理为埃氏筛、线性筛）

#include <iostream>
#include <vector>

using namespace std;

int countPrimes(int n) {
    vector<bool> is_prime(n, true); // 初始化所有数都是质数
    vector<int> primes;             // 存储找到的质数

    for (int i = 2; i < n; ++i) {
        if (is_prime[i]) {         // 如果当前数仍然是质数
            primes.push_back(i);   // 将其加入质数数组
        }
        for (int j = 0; j < primes.size() && i * primes[j] < n; ++j) {
            // 遍历已有的质数进行筛选
            is_prime[i * primes[j]] = false;
            if (i % primes[j] == 0) break; // 当前数的质因子已经被筛选过了
        }
    }

    return primes.size();
}

int main() {
    int n = 10;
    int cnt = countPrimes(n);
    cout << cnt << endl; // 4

    return 0;
}

import java.util.ArrayList;
import java.util.List;

public class Main {

    public static int countPrimes(int n) {
        boolean[] isPrime = new boolean[n];
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i < n; ++i) {
            if (!isPrime[i]) {
                primes.add(i);
            }
            for (int j = 0; j < primes.size() && i * primes.get(j) < n; ++j) {
                isPrime[i * primes.get(j)] = true;
                if (i % primes.get(j) == 0) break;
            }
        }
        return primes.size();
    }

    public static void main(String[] args) {
        int n = 10;
        int cnt = countPrimes(n);
        System.out.println(cnt); // 4
    }
}