欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 204. Count Primes

程序员文章站 2022-07-15 09:47:25
...

题目

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.

这道题也是之前水算法作业的时候做过的,但是那个算法已经忘了,好在一看之前的笔记就又记起来了,但是最后实现的时候又踩了无数个坑……

埃拉托色尼筛法的主要思想是,每次找到一个质数,就可以将它的所有倍数标记为非质数。它的主要用途是找到一定范围内的所有质数,而并不是可以直接应用于判断一个数是否为质数,这里就是第一个踩的坑,因为这道题直接求的是一个范围内所有质数的数量。再贴一次图,直观。

LeetCode 204. Count Primes

那么开始写代码了,需要用一个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