leetcode筆記：Count Primes

一. 題目描述

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

二. 題目分析

題目有很多tips，大意是算出2 ~ n之間有多少個素數。

若使用暴力法只會是超時，而正確的思路來自著名的埃拉托斯特尼篩法。簡單來說，要得到自然數n以內的全部素數，必須把不大於sqrt(n)的所有素數的倍數剔除，剩下的就是素數。更多關於埃拉托斯特尼篩法，參照：
http://baike.baidu.com/link?url=A3VQVwl7tDk2aFKcEF6r5jIA_4dZtdw9QnyynKWW9u-2ZPEPcLrrd_hfVzyr94YuIYbhBfeoDrtWlxaSXaE9Lq

而在篩選過程中，也是有技巧的，以下第一種寫法是建立一個大小為n的數組，經過初始化後：

從2開始將素數的倍數都標注為不是素數。第一輪將4、6、8、10...等標識為非素數；
然後遍歷3的倍數，首先發現3沒有被標記為非素數，因此將6、9、12、15...等標識為非素數；
遍歷4的倍數，發現4本身就不是素數，它的倍數更不可能為素數，可跳過；

重復以上步驟一直遍歷到n為止，再數一遍素數數組中有多少素數。

三. 示例代碼

// 較為耗時，AC，400+ms
class Solution {
public:
    int countPrimes(int n) {
        vector numFlag(n, true);
        int count = 0;
        for (int i = 2; i < n; ++i)
            if (numFlag[i] == true)
                for (int j = i * 2; j < n; j = j + i)
                    numFlag[j] = false; // 成倍數的數均不是質數

        for (int i = 2; i < n; ++i)
            if (numFlag[i]) ++count;
        return count;
    }
};

// 更少的循環次數，AC, 12ms
int countPrimes(int n) {
    if(--n < 2) return 0;
    int m = (n + 1)/2, count = m, k, u = (sqrt(n) - 1)/2;
    bool notPrime[m] = {0};

    for(int i = 1; i <= u; i++)
        if(!notPrime[i])
          for(k = (i+ 1)*2*i; k < m; k += i*2 + 1)
              if (!notPrime[k])
              {
                  notPrime[k] = true;
                  count--;
              }
    return count;
}

四. 小結

最後，分享網上一種娛樂的解法，效率絕對是最高的：

class Solution {
public:
    int countPrimes(int n) {
        switch(n) {
            case 0:
            case 1:
            case 2: return 0;
            case 3: return 1;
            case 4:
            case 5: return 2;
            case 6: 
            case 7: return 3;
            case 8:
            case 9: 
            case 10: 
            case 11: return 4;
            case 12: 
            case 13: return 5;
            case 14: 
            case 15: return 6;
            case 10000: return 1229;
            case 499979: return 41537;
            case 999983: return 78497;
            case 1500000: return 114155;
        }
    }
};