题解 | #判断质数#

题目链接

判断质数

题目描述

给定一个正整数 $n$ ，请判断 $n$ 是否为质数。

质数是指仅能被 $1$ 和其自身整除、且大于 $1$ 的正整数。

解题思路

判断一个数 $n$ 是否为质数，最直接的方法是试除法。

处理特殊情况：根据质数的定义，小于或等于 $1$ 的数都不是质数。所以如果 $n \le 1$ ，可以直接判定为“No”。
处理数据范围：题目给定的 $n$ 最大可达 $10^{12}$ ，这个值超过了标准 int 类型的存储范围。因此，我们需要使用 64 位整型，即 C++ 中的 long long 或 Java 中的 long 来存储 $n$ 。
试除法：对于一个大于 $1$ 的整数 $n$ ，我们检查从 $2$ 到 $\sqrt{n}$ 的所有整数，看它们是否能整除 $n$ 。
- 如果在这个范围内找到了任何一个数 $i$ 能够整除 $n$ （即 $n \pmod i = 0$ ），那么 $n$ 至少有 $1$ 、 $i$ 和 $n$ 这三个因子（如果 $i \ne n$ ），所以 $n$ 不是质数，可以直接返回“No”。
- 如果检查完从 $2$ 到 $\sqrt{n}$ 的所有数都没有找到能整除 $n$ 的，那么 $n$ 就是质数。
为什么检查到 $\sqrt{n}$ 就足够了？
- 因为如果一个数 $n$ 有一个大于 $\sqrt{n}$ 的因子 $a$ ，那么它必然也有一个小于 $\sqrt{n}$ 的因子 $b$ ，满足 $n = a \cdot b$ 。
- 例如，如果 $a > \sqrt{n}$ ，那么 $b = n/a < n/\sqrt{n} = \sqrt{n}$ 。
- 所以，如果我们没能在 $[2, \sqrt{n}]$ 的范围内找到 $n$ 的任何因子，那么它在 $(\sqrt{n}, n)$ 的范围内也必然不会有因子。

代码

c++
java
python

#include <iostream>
#include <cmath>

using namespace std;
using LL = long long;

// 判断一个数是否为质数
bool is_prime(LL n) {
    if (n <= 1) {
        return false; // 小于等于1的数不是质数
    }
    // 从2遍历到sqrt(n)
    // 循环变量i也需要是long long，防止 i*i 溢出
    for (LL i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            return false; // 发现了因子，不是质数
        }
    }
    return true; // 没有发现因子，是质数
}

int main() {
    LL n;
    cin >> n;
    if (is_prime(n)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    // 判断一个数是否为质数
    public static boolean isPrime(long n) {
        if (n <= 1) {
            return false; // 小于等于1的数不是质数
        }
        // 从2遍历到sqrt(n)
        // 循环变量i也需要是long，防止 i*i 溢出
        for (long i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                return false; // 发现了因子，不是质数
            }
        }
        return true; // 没有发现因子，是质数
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        if (isPrime(n)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

import math

# 判断一个数是否为质数
def is_prime(n):
    if n <= 1:
        return False # 小于等于1的数不是质数
    
    # 从2遍历到sqrt(n)
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False # 发现了因子，不是质数
    return True # 没有发现因子，是质数

# Python的int类型可以处理任意大小的整数，所以不需要特殊修改
n = int(input())
if is_prime(n):
    print("Yes")
else:
    print("No")

算法及复杂度

算法：试除法
时间复杂度： $O(\sqrt{n})$ ，因为循环的上界是 $\sqrt{n}$ 。对于 $n=10^{12}$ ，运算次数约为 $10^6$ ，可以在时间限制内完成。
空间复杂度： $O(1)$ ，我们只使用了常数个额外变量。