欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

“n以内质数个数/素数个数” 的算法

程序员文章站 2022-03-13 09:59:18
...

本人渣笔记本使用Java能在14秒内计算完int上限2147483647内的质数、6秒内计算完10亿内的质数个数

以下代码供大家参考:

public static int PrimeCount(int a) {
        if (a <= 1) return 0;
        int N = (a - 1) / 2;  //只考虑奇数  空间占用减半
        int count = 1;//初始值为1,  忽略 2 这个质数
        boolean[] bl = new boolean[N + 1];//默认为false
        int i = 1;  //对应值为2i+1    3、5、7、9
        int p = 4;  //对应2P+1,即i平方  9  25  49  81
        while (p <= N) { //当N≥4  ,即a≥9(对应i平方)时 门进入循环
            if (!bl[i]) {
                count++;
                for (int j = p; j <= N; j += 2 * i + 1) bl[j] = true;//将大于i平方的奇数倍排除
            }
            /*这两步为了对应值的  p = i*i */
            i++;
            p += 4 * i;
        }
        //读取剩余的质数
        while (i <= N) {
            if (!bl[i]) count++;
            i++;
        }
        return count;
    }

欢迎各位大佬、萌新交流学习!

相关标签: java 算法