源本科技 | 码上会

logo
源本科技 码上会
一站式数字化转型技能学习平台

判断素数

2026/01/26
33
0

题目

判断 101-200 之间有多少个素数，并输出所有素数

运行示例

101 到 200 之间的素数有：
101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 
共有 21 个素数。
👈点击左箭头查看答案（一定要在自己思考并实现后再看参考答案哦！）

解法

一个大于 1 的自然数，若不能被 2 到 √n 之间任何整数整除，则它是素数。
这是因为：如果 n = a × b，且 a ≤ b，那么 a ≤ √n。所以只要检查到 √n 即可。

public class Demo02 {
    public static void main(String[] args) {
        int count = 0;
        System.out.println("101 到 200 之间的素数有：");

        for (int i = 101; i <= 200; i++) {
            if (isPrime(i)) {
                System.out.print(i + " ");
                count++;
            }
        }

        System.out.println("\n共有 " + count + " 个素数。");
    }

    // 判断一个数是否为素数
    public static boolean isPrime(int n) {
        if (n < 2) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false; // 排除偶数（除2外）

        // 只需检查奇数因子到 sqrt(n)
        for (int j = 3; j * j <= n; j += 2) {
            if (n % j == 0) {
                return false;
            }
        }
        return true;
    }
}

总结

  • 素数判断核心：试除到 √n。

  • 性能关键：跳过偶数、减少循环次数。

  • 题目要求：严格限定范围 101–200。

  • 最终答案：该区间内共有 21 个素数。

此解法时间复杂度约为 O(n√n / 2)，在 100 个数的范围内非常高效。