Description:
Count the number of prime numbers less than a non-negative number, n.
思路：用一个数组标记小于n的所有数字是否是质数。
外层从2开始遍历到n-1，内层也从2开始遍历，把内外层所有乘积值标记（乘积得到的数肯定不是质数了）。
public int countPrimes(int n) {
int res = 0;
boolean[] flags = new boolean[n];
for (int i = 2; i < n; i++) {
if (!flags[i]) {
res++;
for (int j = 2; i*j < n; j++) {
flags[i*j] = true;
}
}
}
return res;
}
LeetCode 204. Count Primes Description Count the number o...
204. Count Primes Count the number of prime numbers less ...
Count Primes Description:Count the number of prime number...
Description:Count the number of prime numbers less than a...
这道题目对时间复杂度要求比较高。先将n个数放入表中，将所有数标记为true。从2开始访问，此时2为true，质数计...
问题： Count the number of prime numbers less than a non-neg...
我的方法超时了，代码如下： 依然超时的办法，代码如下： 传说的## 厄拉多塞筛法
Description: Count the number of prime numbers less than ...
1.描述 Description: Count the number of prime numbers less ...
n以内素数的个数。 参考：埃拉托斯特尼筛法和素数判断 代码：
本文标题：Leetcode 204. Count Primes
本文链接：https://www.haomeiwen.com/subject/yeigvxtx.html
网友评论