LeetCode 质数计数(厄拉多塞筛法)
问题:
统计所有小于非负整数 n 的质数的数量。
示例:
输入:n = 10
输出:4
解释:小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
优化做法:
厄拉多塞筛法:
算法详解及图片展示
代码:
public static int countPrime(int n){
int count = 0;
boolean[] signs = new boolean[n];
for (int i = 0; i < n;i++){
signs[i] = true;
}
for (int i = 2; i < n; i++){
if(signs[i]) {
count++;
for (int j = i + i ; j < n ;j += i){
signs[j] = false;
}
}
}
return count;
}
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
二维码