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

题目

判断一个数是否为素数

思路

本题判断一个数是否为素数（大于 1 且只能被 1 和自身整除）。 若 n<2 则不是素数。否则用 i 从 2 试到 sqrt(n)（或 i*i<=n），若存在整除则不是；全部试完则是素数。

解题分析

素数判断只需试到 √n：若存在因子 d，则 n/d 也成对出现，较小那个不超过 √n。n<2 直接否，2 单独是素数，偶数大于 2 可直接否再试奇数因子。

完整程序

import java.io.*;

public class Main {
    public static void main(String[] args) {
        int n = 17;
        if (n < 2) {
            System.out.println("no");
            return;
        }
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                System.out.println("no");
                return;
            }
        }
        System.out.println("yes");
    }
}

运行示例

输出：

yes