题解 | #素数判断#

题目链接

素数判断

题目描述

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

输入描述: 第一行输入一个整数 t，表示有 t 组测试数据。接下来 t 行，每行输入一个正整数 n。

输出描述: 对于每组测试数据，输出一行。如果 n 是素数，则输出 "Yes"；否则，输出 "No"。

解题思路

本题需要实现一个函数来判断一个给定的数 n 是否为素数。核心是理解素数的定义并用高效的算法实现。

处理输入: 首先，根据题目要求，我们需要读取一个整数 t，然后循环 t 次，在每次循环中读取待判断的数字 n。
素数判断逻辑 (Trial Division - 试除法):
- 基本定义: 素数是大于 1 且只能被 1 和自身整除的数。
- 特殊情况: 根据定义，1 不是素数。所以如果输入的 n 小于等于 1，可以直接判定为 "No"。
- 暴力检查: 一个简单的想法是，从 2 遍历到 n-1，检查是否有任何数能整除 n。如果找到一个，n 就不是素数。如果遍历完都没有找到，n 就是素数。
- 优化: 我们可以对暴力检查进行一个关键的优化。如果一个数 d 能整除 n，那么 n/d 也能整除 n。这两个因数 d 和 n/d 中，必然有一个小于或等于 sqrt(n)。例如，对于 n=36，因数对有 (2, 18), (3, 12), (4, 9), (6, 6)。可以看到，每对因数中较小的一个总是 <= sqrt(36) = 6。因此，我们只需要检查从 2 到 sqrt(n) 的所有整数 i 是否能整除 n 即可。如果在这个范围内都找不到因数，那么 n 一定是素数。
算法步骤:
- 读取 t。
- 循环 t 次：
  - 读取 n。
  - 如果 n <= 1，输出 "No"。
  - 否则，设置一个标志位 isPrime = true。
  - 循环 i 从 2 到 sqrt(n)：
    - 如果 n % i == 0，说明 n 有一个因数 i，它不是素数。将 isPrime 设为 false 并 break 内部循环。
  - 根据 isPrime 的最终值，输出 "Yes" 或 "No"。

代码

c++
java
python

#include <iostream>
#include <cmath>

using namespace std;

// 判断是否为素数的函数
bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }
    for (int i = 2; i <= sqrt(n); ++i) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        if (isPrime(n)) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    // 判断是否为素数的函数
    public static boolean isPrime(int n) {
        if (n <= 1) {
            return false;
        }
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

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

import math

def is_prime(n):
    if n <= 1:
        return False
    # 遍历到 n 的平方根即可
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

# 读取测试用例的数量
t = int(input())
for _ in range(t):
    n = int(input())
    if is_prime(n):
        print("Yes")
    else:
        print("No")

算法及复杂度

算法：试除法（Trial Division）。
时间复杂度：对于每个数 n 的判断需要 $\mathcal{O}(\sqrt{n})$ 的时间。总共有 t 个测试用例，所以总时间复杂度是 $\mathcal{O}(t \cdot \sqrt{n_{max}})$ ，其中 n_{max} 是 n 的最大可能值。
空间复杂度： $\mathcal{O}(1)$ ，我们只使用了常数级别的额外空间。