2.统计素数（质数）个数

最新推荐文章于 2025-04-17 10:15:49 发布

、wook

最新推荐文章于 2025-04-17 10:15:49 发布

阅读量1.6k

点赞数 1

文章标签：算法

本文链接：https://blog.csdn.net/evelynnJava/article/details/122246747

版权

从零开始的算法专栏收录该内容

4 篇文章

订阅专栏

题目：统计素数个数。

素数：只能被1和自身整除的数，0、1除外

解法一：暴力算法

public class Sushu {
    public static void main(String[] args) {
        System.out.println(countPrimes(100));
    }

    public static int countPrimes(int n) {
        int ans = 0;
        for (int i = 2; i < n; ++i) {
            ans += isPrime(i) ? 1 : 0;
        }
        return ans;
    }

    /**
     * 是否为素数
     */
    public static boolean isPrime(int x) {
        for (int i = 2; i < x; ++i) {
            //除了1和自身的任意数，取模存在等于0的，则非素数
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
}

结果：100以内有25个素数

冷知识：for循环第3语句块 ++i 和 i++效果一样，但是 ++i 性能好一些。i++由于是在使用当前值之后再+1，所以需要一个临时的变量来转存。

即使暴力破解，也是有优化空间的。
上面的程序 isPrime ，在 x = 素数时，例11，需要遍历9次（ 11%2 11%3 11%4 11%5 11%6 11%7 11%8 11%9 11%10）才能知道这个数字是素数。我们可以利用开根号的方式，减少遍历次数。

//i如果能被x整除，则x/i肯定能被x整除，因此只需判断i和根号x之中较小的即可
    public boolean isPrime(int x) {
        for (int i = 2; i * i <= x; ++i) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }

说明：
11%2 理解为 11/2 = 5 ， 11%3 理解为 11/3 = 3，11/4 = 2，之后的 11/5 = 2 其实和最开始的 11/2是没有区别的，所以实际上没有必要再去算 11/5 之后的程序，可以理解为开根号是为了得到临界值

故使用根号推算： 由原来的 i < x 变为 i < √x （也可以使用 Math中的根号方法），此处我们没有用，所以左右一起加平方，即 i * i <= x

解法二：埃式筛选法

例 2 * 3，2 * 4 ，肯定等于非素数（合数），所以我们的目标就是省去合数的遍历次数。

public class Sushu {
    public static void main(String[] args) {
        System.out.println(eratosthenes(100));
    }

    public static int eratosthenes(int n) {
        boolean[] isPrime = new boolean[n];
        //初始假定小于n的所有数都为素数
        Arrays.fill(isPrime,true);
        int ans = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) {
                ans += 1;
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        return ans;
    }
}