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

我不是女神ヾ 2024-03-16 17:06 12阅读 0赞

## 数据结构与算法面试题：给定非负整数 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 i i是否为质数，初始默认为`true`。从2开始枚举每个数，如果其是质数，则将其加入质数数组中，并筛掉它的所有合数。具体实现时，在已知当前数是质数的情况下，可以用质数去筛选更大的合数。而为了能够正确并快速地找出合数进行筛选，我们维护一个质数数组，该数组存储已有的所有质数。对于每个数 i i i，我们遍历已有的质数，逐一去除掉其倍数。注意到当质因子超过 n \\sqrt n n时，它的倍数必然小于 n n n，所以算法不需要再遍历它的倍数。最后输出质数数目即可。

*  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
        }
    }