1 题目Description:Count the number of prime numbers less than a non-negative number, n.接口:public int countPrimes(int n);2 思路统计小于n的素数个数,注意不包括n。思路1:素数的判断很容易想到素数的判断isPrime,然后逐个数来进行判断是否是素数。进行统计,输出结果。复杂度: 把isPrime时间复杂度控制在O(n^0.5)的话,因此:Time:O(n^1.5) , Space:O(1)。提交代码仍然超时。思路2: 素数表素数表的产生,在[1 to n)的范围内,标记出 非素数,剩下的就是素数了。思路:初始化所有的[2,n)都是素数剔除掉非素数统计素数个数如何标记 非素数呢?分组标记:2,[4,6,8,10,12,14,16,18,20,22,24...];3,[9,12,15,18,21,24,27,...];5,[25,30,35...]考虑一下终止条件复杂度: Time: O(n log log n) , Space: O(n)3 代码思路1// 判断一个数是否是素数的方法:不是最好,但还可以。素数表是判断素数的好方法。// Time:O(sqrt(n)) Space:O(1)boolean isPrime(int n) {for (int i = 2; (i
...
继续阅读
(19)