题目描述(简单难度)
求出小于 的素数个数。
解法一
遍历 2
到 n - 1
,依次判断当前数是否是素数。
判断 n
是否是素数,只需要判断 2
到 n - 1
是否是 n
的因子,如果有一个是,那就表明 n
不是素数。
判断素数可以做一个优化,那就是不需要判断 2
到 n - 1
,只需要判断2
到 sqrt(n)
也就是根号 n
即可。因为如果存在超过根号 n
的因子,那么一定存在小于根号 n
的数与之对应。
解法二
用一个数组表示当前数是否是素数。
然后从 2
开始,将 的倍数,4
、6
、8
、10
…依次标记为非素数。
下个素数 3
,将 3
的倍数,6
、9
、12
、15
…依次标记为非素数。
下个素数 7
,将 7
的倍数,14
、21
、28
、 …依次标记为非素数。
public int countPrimes(int n) {
boolean[] notPrime = new boolean[n];
for (int i = 2; i < n; i++) {
if (!notPrime[i]) {
count++;
//将当前素数的倍数依次标记为非素数
for (int j = 2; j * i < n; j++) {
}
}
}
}
总
解法二中空间换时间的思想在编程中经常用到。
添加好友一起进步~
如果觉得有帮助的话,可以点击 这里 给一个 star 哦 ^^