题目链接：Count Primes

Description:

Count the number of prime numbers less than a non-negative number, n.

References:

How Many Primes Are There?

Sieve of Eratosthenes

这道题的要求是统计小于n的非负整数中有多少质数。

常用的快速方法是埃拉托斯特尼筛法：给出要筛数值的范围n，找出sqrt(n)以内的素数p1, p2, …, pk。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个素数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个素数5筛，把5留下，把5的倍数剔除掉；不断重复下去……

  1. Plan A

采用vector构造长度为n的数组，进行筛选，时间321ms。

时间复杂度：O(n(logn)(loglogn))

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution
{
public:
    int countPrimes(int n)
    {
        vector<bool> prime(n, true);
        
        int sqrn = sqrt(n);
        for(int i = 2; i <= sqrn; ++ i)
            if(prime[i])
                for(int j = i * i; j < n; j += i)
                    prime[j] = false;
        
        int res = 0;
        for(int i = 2; i < n; ++ i)
            if(prime[i])
                ++ res;
        return res;
    }
};

  1. Plan B

采用new操作构造长度为n的数组，进行筛选，时间59ms。

时间复杂度：O(n(logn)(loglogn))

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution
{
public:
    int countPrimes(int n)
    {
        bool *prime = new bool[n];
        for(int i = 0; i < n; ++ i)
            prime[i] = true;
        
        int sqrn = sqrt(n);
        for(int i = 2; i <= sqrn; ++ i)
            if(prime[i])
                for(int j = i * i; j < n; j += i)
                    prime[j] = false;
        
        int res = 0;
        for(int i = 2; i < n; ++ i)
            if(prime[i])
                ++ res;
        
        return res;
    }
};

  1. Plan C

采用new操作构造长度为n的数组，进行筛选（一次遍历），时间45ms。

时间复杂度：O(n(logn)(loglogn))

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution
{
public:
    int countPrimes(int n)
    {
        bool *visited = new bool[n];
        
        int sqrn = sqrt(n), res = 0;
        for(int i = 2; i < n; ++ i)
            if(!visited[i])
            {
                ++ res;
                if(i <= sqrn)
                    for(int j = i * i; j < n; j += i)
                        visited[j] = true;
            }
        
        return res;
    }
};

  1. Plan D

采用new操作构造int数组，位操作统计，时间65ms。

时间复杂度：O(n(logn)(loglogn))

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution
{
public:
    int countPrimes(int n)
    {
        int bit_num = sizeof(int) * 8;
        int *is_prime = new int[n / bit_num + 1];
        is_prime[0] = -1 & ~3;
        for(int i = 1; i < n / bit_num + 1; ++ i)
            is_prime[i] = -1;
        
        int sqrn = sqrt(n);
        for(int i = 2; i <= sqrn; ++ i)
            if(is_prime[i / bit_num] & (1 << i % bit_num))
                for(int j = i * i; j < n; j += i)
                    is_prime[j / bit_num] &= ~(1 << j % bit_num);
        
        int res = 0;
        for(int i = 0; i < n / bit_num; ++ i)
            res += hammingWeight(is_prime[i]);
        for(int i = n / bit_num * bit_num; i < n; ++ i)
            if(is_prime[i / bit_num] & (1 << i % bit_num))
                ++ res;    
        return res;
    }
private:
    int hammingWeight(int n)
    {
        n = (n & 0x55555555) + (n >>  1 & 0x55555555);
        n = (n & 0x33333333) + (n >>  2 & 0x33333333);
        n = (n & 0x0F0F0F0F) + (n >>  4 & 0x0F0F0F0F);
        n = (n & 0x00FF00FF) + (n >>  8 & 0x00FF00FF);
        n = (n & 0x0000FFFF) + (n >> 16 & 0x0000FFFF);
        return n;
    }
};