数据结构与算法面试题：给定非负整数 m 和 n，计算不大于 m 的数字中，素数的个数。（提示：算法原理为埃氏筛、线性筛）
简介：数据结构与算法面试题：给定非负整数 m 和 n，计算不大于 m 的数字中，素数的个数。（提示：算法原理为埃氏筛、线性筛）
算法思路
算法思路：
根据题意，题目需要计算不大于m的素数个数。首先需要判断一个整数是否是素数，然后累加素数个数即可。
最常用的判断素数方法就是试除法，假设要判断n是否为素数，只需要从2到n-1试图去整除它，如果发现有除了1和自身以外的因子，则n不是素数；否则n是素数。但是直接进行此方法所需要的时间复杂度O(n)非常高，无法满足实际需求。而为了尽可能提高效率，可以使用埃氏筛或线性筛来找出素数。
埃氏筛：
从1到m枚举每个数，判断其是否被之前的数筛除，如果没有，则把该数的所有倍数都标记成合数（被筛除）。实现时可以将质数放入容器中，筛掉合数时可以跳过已经筛选过的质数，这样可以提高效率，时间复杂度为O ( n l o g l o g n ) O(nloglogn)O(nloglogn)。
线性筛：
类似埃氏筛，但是在筛时用小质数去筛选合数，剩下没有被筛去的数就是质数。例如第一次会标记2的倍数为合数，第二次会标记3的倍数为合数，以此类推。但是需要注意的是，一个合数可能会被多个质数筛选，因此对于每个数只能被标记一次。时间复杂度为O ( n ) O(n)O(n)。
因为线性筛法效果更好，所以下面给出的是线性筛算法的实现：
#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; }
其中is_prime[i]表示数字i ii是否为质数，初始默认为true。从2开始枚举每个数，如果其是质数，则将其加入质数数组中，并筛掉它的所有合数。具体实现时，在已知当前数是质数的情况下，可以用质数去筛选更大的合数。而为了能够正确并快速地找出合数进行筛选，我们维护一个质数数组，该数组存储已有的所有质数。对于每个数i ii，我们遍历已有的质数，逐一去除掉其倍数。注意到当质因子超过n \sqrt nn时，它的倍数必然小于n nn，所以算法不需要再遍历它的倍数。最后输出质数数目即可。
- Java版本
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 } }
