经典之作：筛选法求素数（埃氏筛与线性筛）
发布时间
阅读量：
阅读量
题目描述
统计小于非负整数n的质数数量
浑水摸鱼之蛮力验证法
直接上代码
bool is_zen(int x) {
int i = 2;
while (i * i <= x) {
if (x % i == 0) {
return 0;
}
i++;
}
return 1;
}
int countPrimes(int n) {
int count = 0;
for (int i = 2; i < n; i++) {
if (is_zen(i)) {
count++;
}
}
return count;
}普遍认为这是许多新手使用的办法，在处理小于n的所有正整数值时，会对每一个数字进行逐一排查以确定其是否为质数。
注意到的是，在质数判定方面，并非需要完全遍历每一个数来检查能否整除（即进行一次完整的遍历），而是只需计算到平方根值√x就可以确定其质数性质。这种优化使得计算过程更加高效且易于理解。
计算时间为O(n\sqrt{n})的算法所需内存空间为常数级$
全部评论 (0)
还没有任何评论哟~