“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;
}
欢迎各位大佬、萌新交流学习!
上一篇: 关于区块链的一些想法
下一篇: 蜘蛛和蜜蜂要结婚了
推荐阅读
-
Python2.7基于笛卡尔积算法实现N个数组的排列组合运算示例
-
设计一个算法,计算出n阶乘中尾部零的个数
-
蓝桥杯 算法训练 - 连续正整数的和 78这个数可以表示为连续正整数的和,1+2+3,18+19+20+21,25+26+27。 输入一个正整数 n(<=10000) 输出 m 行(n有m
-
输入正整数n(n大于等于2),求不大于n的全部质数(素数)【其中一种优化算法】
-
php 把一个数组分成有n个元素的二维数组的算法
-
如何编程最快速度求出两百万以内素数个数(不限语言和算法)?
-
基础算法:给定一个无序数组,包含正数、负数和0,要求从中找出3个数的乘积,使得乘积最大,要求时间复杂度:O(n),空间复杂度:O(1)
-
给定n个整数的数组A以及一个数x,设计一个分治算法,求出x在数组中出现的次数,并分析时间复杂度
-
【算法:Java实现】判断一个数是否是2的N次方
-
【算法】从1到n中1出现的个数