Java第21题：判断一个数是否为素数

题目

从标准输入读入一个整数 n，判断其是否为质数（素数）。质数是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的数。

输入格式：一行输入一个整数 n。

输出格式：若是素数输出 yes，否则输出 no，末尾换行。

数据范围与约定：-10⁹ ≤ n ≤ 10⁹。

思路与算法

1. 特殊与非素数拦截
所有小于等于 1 的整数都不是素数；2 是最小的素数，也是唯一的偶素数。

2. 试除法边界 √n
若整数 n 有因数 d，则必有对应因数 n/d，其中较小者必然满足 d ≤ √n。因此试除只需从 2 检查到 i * i ≤ n，一旦整除即可判定合数提前退出，时间复杂度为 O(√n)。

完整程序

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        // 0 和 1 既不是素数也不是合数，负数也不是素数
        if (n < 2) {
            System.out.println("no");
            return;
        }

        // 核心优化：因子成对出现，较小者必 <= √n
        // 用 (long) i * i <= n 替代 Math.sqrt(n)，避免浮点运算开销与精度偏差
        boolean isPrime = true;
        for (int i = 2; (long) i * i <= n; i++) {
            if (n % i == 0) {
                isPrime = false;
                break;
            }
        }

        System.out.println(isPrime ? "yes" : "no");
    }
}

运行示例

输入：

17

输出：

yes