LeetCode 204. Count Primes
题目:
Count the number of prime numbers less than a non-negative number, n.
Example:
Input: 10 Output: 4 Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
这道题也是之前水算法作业的时候做过的,但是那个算法已经忘了,好在一看之前的笔记就又记起来了,但是最后实现的时候又踩了无数个坑……
埃拉托色尼筛法的主要思想是,每次找到一个质数,就可以将它的所有倍数标记为非质数。它的主要用途是找到一定范围内的所有质数,而并不是可以直接应用于判断一个数是否为质数,这里就是第一个踩的坑,因为这道题直接求的是一个范围内所有质数的数量。再贴一次图,直观。
那么开始写代码了,需要用一个vector存放这个范围内的所有数字是否是质数。
首先是关于外层循环的upper bound,和最原始的判断质数的方法一样,也是循环到开根号为止就行了,为什么呢,这个我似乎解释不清楚。我的感觉是,对于乘法来说,肯定是小于根号n的一个数 乘 大于根号n的一个数,再加上所有的合数都可以分解质因数成若干个质数之积,所以在根号n到n之间出现的合数,一定会被小于根号n的一个数字以倍数的形式找到。不知道这么解释对不对orz
然后是内层循环,注意不能把判断是否为质数的if语句合并到外层循环中的第二条,因为第二条是截止条件啊一触发就再也不进行下去了QAQAQ 这种愚蠢的低级错误怎么也犯了,还想半天想不通为啥不行……
继续内层循环,设置一个新的变量进行循环,这个变量的设置就很有讲究了。刚开始我一直想的是设置一个j=2(刚开始没想清楚还想着j从1开始真是没救了),然后j<n/i就完事了,但是却忽略了除法的不精确性(比如小数点就直接省了),所以这里要用乘法写才比较安全,i*j<n也是一样的效果,以后都要注意这个问题。这里还有另外一种写法,就是把j设为i*i,然后j<n,j+=i,这个就更加巧妙了,因为比i*i小的i的倍数之前肯定被某个比i小的质数给处理过了,但是好像看到有人提到了i*i可能会overflow,这个还没仔细研究。
最后的最后,submit了才发现,n=0的情况不管怎么样都要单独拎出来,因为你不能设置一个长度为0的vector然后给它搞出1……
以下是代码,时间复杂度据说是O(n log log n),运行80ms,42.39%,空间复杂度O(n),8.7M,58.33%:
class Solution {
public:
int countPrimes(int n) {
if (n == 0) {
return 0;
}
vector<bool> primes(n, true);
primes[0] = false;
primes[1] = false;
for (int i = 0; i < sqrt(n); i++) {
if (primes[i]) {
for (int j = 2; j * i < n; j++) {
primes[i * j] = false;
}
/* for (int j = i * i; j < n; j += i) {
primes[j] = false;
} */
}
}
return count(primes.begin(), primes.end(), true);
}
};
还看到一个这个算法的更加改进版,懒得看了,贴个链接:https://leetcode.com/problems/count-primes/discuss/57593/12-ms-Java-solution-modified-from-the-hint-method-beats-99.95
上一篇: Java入门
下一篇: 1267. 统计参与通信的服务器
推荐阅读
-
LeetCode - 38. Count and Say(36ms)
-
leetcode【字符串】-----38. Count and Say(报数)
-
Leetcode1-100: 38. Count and Say
-
LeetCode 38. Count and Say 报数(Java)
-
LeetCode 204. 计数质数 263. 丑数 264. 丑数 II
-
【Hard 递归 动态规划 回文串15】LeetCode 730. Count Different Palindromic Subsequences
-
Leetcode#204. Count Primes
-
LeetCode 204. Count Primes
-
LeetCode ---204. Count Primes
-
【leetcode】204. Count Primes