程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> leetcode筆記:Count Primes

leetcode筆記:Count Primes

編輯:C++入門知識

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;
        }
    }
};

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved