题解 | #判断质数#

题目链接

判断质数

题目描述

给定一个正整数 $n$ ，请判断 $n$ 是否为质数。质数的定义是：在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。

解题思路

判断一个数 $n$ 是否为质数，最直观的方法是尝试用从 $2$ 到 $n-1$ 的所有整数去除 $n$ ，如果都不能整除，那么 $n$ 就是质数。但是这种方法效率较低。我们可以对其进行优化。

核心思想：试除法优化

一个重要的数学性质是：如果一个数 $n$ 有一个因数 $d$ ，那么它必然有另一个因数 $n/d$ 。这两个因数中，必然有一个不大于 $\sqrt{n}$ ，另一个不小于 $\sqrt{n}$ 。

例如，对于 $n=36$ ， $\sqrt{36}=6$ 。
- 因数 $2$ 对应因数 $18$ ，其中 $2 \le 6$ 。
- 因数 $3$ 对应因数 $12$ ，其中 $3 \le 6$ 。
- 因数 $4$ 对应因数 $9$ ，其中 $4 \le 6$ 。
- 因数 $6$ 对应因数 $6$ ，其中 $6 \le 6$ 。

这意味着，如果 $n$ 不是质数，它必定存在一个小于或等于 $\sqrt{n}$ 的因数。反之，如果我们检查了从 $2$ 到 $\sqrt{n}$ 的所有整数，都不能整除 $n$ ，那么 $n$ 就不可能再有其他因数了（除了1和它自身），因此 $n$ 必定是质数。

算法步骤

处理特殊情况：
- 如果 $n \le 1$ ，根据定义，它不是质数。
试除：
- 从 $i=2$ 开始，循环直到 $i \cdot i \le n$ （这等价于 $i \le \sqrt{n}$ ，但避免了浮点数计算，更高效且精确）。
- 在循环中，检查 $n$ 是否能被 $i$ 整除（即 n % i == 0）。
- 如果能整除，说明 $n$ 有一个小于自身的因数 $i$ ，因此 $n$ 不是质数，可以直接返回 No。
最终判断：
- 如果循环正常结束，没有找到任何能整除 $n$ 的数，说明 $n$ 是质数，返回 Yes。

代码

c++
java
python

#include <iostream>
#include <cmath>

using namespace std;

bool is_prime(long long n) {
    if (n <= 1) {
        return false;
    }
    for (long long i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

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

import java.util.Scanner;

public class Main {
    public static boolean isPrime(long n) {
        if (n <= 1) {
            return false;
        }
        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
    # 遍历到 int(sqrt(n)) + 1 即可
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

def solve():
    n = int(input())
    if is_prime(n):
        print("Yes")
    else:
        print("No")

solve()

算法及复杂度

算法：试除法
时间复杂度：我们需要循环大约 $\sqrt{n}$ 次来检查是否存在因数。因此，时间复杂度为 $\mathcal{O}(\sqrt{n})$ 。
空间复杂度：我们只使用了少数几个变量来存储中间值，所以空间复杂度为 $\mathcal{O}(1)$ 。