埃氏筛选-判断素数

核心思路如下：

初始化：创建一个布尔数组 isshushu，其长度等于要检查的数 n。这个数组用于标记每个数是否为质数，初始时所有数都假设为质数（即数组元素均为 false）。

筛选：从最小的质数2开始，将它的所有倍数标记为合数（非质数），即把 isshushu 数组中对应索引位置的值设置为 true。由于一个数的质因数必定小于或等于它的平方根，所以只需要检查到 sqrt(n) 即可。

计数：在筛选过程中，每当遇到一个未被标记为合数的数（即 isshushu 数组中对应值为 false 的数），则它就是一个质数，增加质数计数器 count 的值。

返回结果：当所有小于 n 的数都经过筛选后，返回质数计数器 count 的值，即小于 n 的质数数量。

通过这种方式，代码能够高效地找出并计算给定范围内质数的数量，避免了逐一检查每个数是否为质数的低效方法。

直接上代码：

public class Solution {
    public static int search(int n) {
        boolean[] isshushu = new boolean[n];
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (!isshushu[i]) {
                count++;
                for (int j = 2 * i; j < n; j += i) {
                    isshushu[j] = true;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int cc=search(100);
        System.out.println(cc);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20