BGN41 判断质数

思路

题目很直白：给你一个正整数 ，判断它是不是质数，是的话输出 Yes，否则输出 No。

那什么是质数？大于 1 的整数，且只能被 1 和自身整除。

怎么判断呢？最朴素的方法是从 2 遍历到 ，看有没有能整除 的数。但这样太慢了，有没有更快的办法？

试除法优化

关键观察：如果 有一个因子 （），那 也是 的因子。 和 这两个因子，至少有一个 。

所以我们只需要从 2 枚举到 就够了。如果在这个范围内没有找到任何因子， 就是质数。

注意数据范围

这道题有个小坑：输入数据可能超过 int 的范围（测试用例中出现了 274876858367 这样的大数）。所以 C++ 要用 long long，Java 要用 long。

循环条件写成 i * i <= n 比调用 sqrt 更好，避免浮点精度问题。

代码

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    if (n < 2) {
        cout << "No" << endl;
        return 0;
    }
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        if (n < 2) {
            System.out.println("No");
            return;
        }
        for (long i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                System.out.println("No");
                return;
            }
        }
        System.out.println("Yes");
    }
}

import math

n = int(input())
if n < 2:
    print("No")
else:
    is_prime = True
    for i in range(2, int(math.isqrt(n)) + 1):
        if n % i == 0:
            is_prime = False
            break
    print("Yes" if is_prime else "No")

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const n = BigInt(lines[0].trim());
    if (n < 2n) {
        console.log("No");
        return;
    }
    let isPrime = true;
    for (let i = 2n; i * i <= n; i++) {
        if (n % i === 0n) {
            isPrime = false;
            break;
        }
    }
    console.log(isPrime ? "Yes" : "No");
});

复杂度分析

  • 时间复杂度：，只需要枚举到 。
  • 空间复杂度：，只用了几个变量。

总结

判断质数是最基础的数论问题之一。核心就是试除法——枚举到 就够了，不需要遍历到 。实际做题时容易忽略的点是数据范围，如果题目没有明确说范围在 int 内，用 long long / long 是更安全的选择。