题解 | #筛法判断质数#

题目链接

筛法判断质数

题目描述

给定 $N$ 个正整数，对于每个整数 $x$ ，请你判断 $x$ 是否为质数（素数）。若是，则输出 Yes，否则输出 No。

解题思路

本题要求对多个数字进行质数判断。如果对每个查询都独立使用试除法（检查从 $2$ 到 $\sqrt{x}$ 的因子），当查询数量巨大时，总时间复杂度可能会很高，导致超时。

考虑到查询的数字范围是固定的，这是一个典型的可以使用预处理来优化的场景。对于质数判断，最经典高效的预处理算法是埃拉托斯特尼筛法（简称埃氏筛）。

核心思想：

埃氏筛的基本思想是，从最小的质数 $2$ 开始，依次将其所有倍数标记为“合数”。然后找到下一个未被标记的数（它必然是质数，例如 $3$ ），再将其所有倍数标记为合数。重复此过程，直到完成筛选。
算法步骤：
- 创建一个布尔数组 $is\_prime$ ，大小为数据范围的上限 $MAX\_X$ ，并初始化所有值为 $\text{true}$ ，代表假设所有数都是质数。
- 根据定义， $0$ 和 $1$ 不是质数，所以设置 $is\_prime[0] = is\_prime[1] = \text{false}$ 。
- 从 $p = 2$ 开始外层循环，循环条件为 $p \cdot p < MAX\_X$ 。
- 在循环中，如果 $is\_prime[p]$ 仍然为 $\text{true}$ ，说明 $p$ 是一个质数。
- 对于这个质数 $p$ ，我们启动一个内层循环，将其所有倍数（从 $p \cdot p$ 开始）都标记为合数，即设置 $is\_prime[j] = \text{false}$ 。
- 优化：内层循环从 $p \cdot p$ 开始，是因为任何小于 $p \cdot p$ 的 $p$ 的倍数，例如 $k \cdot p$ ( $k < p$ )，必然有一个小于 $p$ 的质因子，因此它已经被前面的步骤筛掉了。
处理查询：
- 在程序开始时，我们先执行一次埃氏筛法，预处理出 $MAX\_X$ 范围内所有数的质数属性。
- 对于接下来的每一个查询 $x$ ，我们只需要直接查找 $is\_prime[x]$ 的值即可，可以在 $\mathcal{O}(1)$ 的时间内得到答案。

代码

c++
java
python

#include <iostream>
#include <vector>

using namespace std;

const int MAX_X = 1000001;
vector<bool> is_prime(MAX_X, true);

void sieve() {
    is_prime[0] = is_prime[1] = false;
    for (int p = 2; p * p < MAX_X; ++p) {
        if (is_prime[p]) {
            for (int i = p * p; i < MAX_X; i += p) {
                is_prime[i] = false;
            }
        }
    }
}

int main() {
    sieve();
    
    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        if (is_prime[x]) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    
    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    static final int MAX_X = 1000001;
    static boolean[] is_prime = new boolean[MAX_X];

    static {
        Arrays.fill(is_prime, true);
        is_prime[0] = is_prime[1] = false;
        for (int p = 2; p * p < MAX_X; p++) {
            if (is_prime[p]) {
                for (int i = p * p; i < MAX_X; i += p) {
                    is_prime[i] = false;
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while (n-- > 0) {
            int x = sc.nextInt();
            if (is_prime[x]) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }
}

MAX_X = 1000001
is_prime = [True] * MAX_X

def sieve():
    is_prime[0] = is_prime[1] = False
    for p in range(2, int(MAX_X**0.5) + 1):
        if is_prime[p]:
            for i in range(p * p, MAX_X, p):
                is_prime[i] = False

def main():
    sieve()
    n = int(input())
    for _ in range(n):
        x = int(input())
        if is_prime[x]:
            print("Yes")
        else:
            print("No")

if __name__ == "__main__":
    main()

算法及复杂度

算法：数论、埃拉托斯特尼筛法
时间复杂度：预处理阶段使用埃氏筛法，时间复杂度为 $\mathcal{O}(M \log \log M)$ ，其中 $M$ 是需要判断的数的最大值。预处理完成后，每次查询的复杂度为 $\mathcal{O}(1)$ 。对于 $N$ 次查询，总时间复杂度为 $\mathcal{O}(M \log \log M + N)$ 。
空间复杂度：需要一个布尔数组来存储每个数是否为质数，空间复杂度为 $\mathcal{O}(M)$ 。