天天看點

LeetCode程式設計練習 - Count Primes學習心得

題目:

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

        給定一個非負數n,求小于n的質數的個數。

思路:

        定義一個變量,初始值為0,用來裝載質數,再定義一個變量周遊所有數,因為第一個質數是2,是以,初始值設為2,用布爾值來判斷是否是質數,若是質數則變量加1。但是顯然結果是不對。

LeetCode程式設計練習 - Count Primes學習心得
LeetCode程式設計練習 - Count Primes學習心得

        解決方案中,每遇到一個數,就判斷它是否能被前面的某一個質數所整除,定義一個數組來存儲質數,每次遇到質數時,将其小于n的倍數都設為非質數,避免每次遇到一個數都要用之前的所有質數去除一遍,降低了時間複雜度。

        方案中相當于對我的思路做了優化,如果有一個數有因子的話,那麼兩個因子至少有一個會是小于等于sqrt(n)的,如果一個數隻要對它的sqrt(n)範圍内進行周遊的話,隻要在這個範圍内是滿足沒有因子的條件,就可認為是質數了,減少了周遊循環的次數,方案使用了埃拉托色尼蘇素數篩法,是一種空間換時間的算法優化,假定範圍内的所有的數都是素數,從2開始,隻要是2的倍數就認為該數不是素數标記,知道判斷到n為止便将所有的非素數标記,進而确定所有非素數。

LeetCode程式設計練習 - Count Primes學習心得
LeetCode程式設計練習 - Count Primes學習心得