LeetCode Count Primes

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.

本题要求从1~n共有多少个素数。Hint里一步步深入写得非常详细了,简要概括一下,有两种方法,一种是常规的从1~n一个个判断是否为非数,另一种是比较巧妙的Hash方法。 常规方法。首先看看判断一个数n是否为素数的方法,因为如果n为合数,则n可以分解为p×q,又n=p×q=(√n)×(√n),假设p是较小数的话,则p≤(√n)。所以我们只需要从2~(√n)判断能否被n整除,时间复杂度为O(n0.5)。从1~n都需要判断是否为素数,所以总的时间复杂度为O(n1.5)。 完整代码如下:

class Solution {
private:
    bool isPrime(int x)
    {
        if (x <= 1)
            return false;
        for (int i = 2; i * i <= x; ++i) {
            if (x % i == 0)
                return false;
        }
        return true;
    }
public:
    int countPrimes(int n)
    {
        int ans = 0;
        for (int i = 1; i < n; ++i) {
            if (isPrime(i))
                ++ans;
        }
        return ans;
    }
};

本代码提交TLE,在n很大的时候无法通过测试。

后来看了Hint,解法还是很巧妙的。如果一个数n是素数,则n的倍数肯定不是素数了,比如2是素数,则4=2*2、6=2*3、8=2*4…这些数肯定就不是素数了。所以我们可以建立一个1~n的Hash表,表示一个数是否为素数。初始的时候Hash[1~n]=true。然后从2开始,如果Hash[i]为true,说明i是素数,则2*i, 3*i,…都不是素数了,即Hash[2*i], Hash[3*i]..=false。如果Hash[i]为false,说明i不是素数,则i可以分解为i=p*q,使得p(或q)为素数,则之前测试p时,已经把p的所有倍数都置为false了,而i的倍数肯定也是p的倍数,所以不需要对i的倍数再置false了。

循环的终止条件是i>(√n),和第一种解法的分析一样,如果某个合数x大于(√n),则其肯定有一个素因子i是小于(√n)的,所以在测试i时,就已经把x置为false了。

另外对于素数i,我们之前分析的是要把所有2*i, 3*i…都置为false。其实这里也可以优化,我们可以从i*i开始置为false,而不需要每次都从2*i开始。比如i=5,常规是要把所有2*5, 3*5, 4*5, 5*5,…都置为false,但其实2*5, 3*5, 4*5都已经被之前的素数2或3置为false了。所以每次我们只需要从i*i开始,下标以i递增的置为false就好。(从i*i到i*i+(i-1)之间的合数被比i小的合数置为false了)总的来说,这一题加速的技巧很多,完整代码如下:

class Solution {
public:
    int countPrimes(int n)
    {
        vector<bool> mark(n, true);
        for (int i = 2; i * i < n; ++i) {
            if (!mark[i])
                continue;
            for (int j = i * i; j < n; j += i) {
                mark[j] = false;
            }
        }
        int ans = 0;
        for (int i = 2; i < n; ++i)
            ans += (mark[i] ? 1 : 0);
        return ans;
    }
};

本代码提交AC,用时29MS。

Leave a Reply

Your email address will not be published. Required fields are marked *