LeetCode演算法題-Count Primes(Java實現)
這是悅樂書的第190 次更新,第193 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第49題(順位題號是204)。計算小於非負數n的素數的數量。例如:
輸入:10
輸出:4
說明:有4個素數小於10,它們是2,3,5,7。
本次解題使用的開發工具是eclipse,jdk使用的版本是1.8,環境是win7 64位系統,使用Java語言編寫和測試。
02 第一種解法
判斷一個數n是否為素數,就需要判斷1到n-1之間的數能否被n整除,能夠被整除說明不是素數,否則就是素數。
public int countPrimes(int n) { if (n <= 2) { return 0; } int count = 0; for (int i=2;i<n; i++) { boolean flag = true; for (int j=2; j<i; j++) { if (i%j == 0) { flag = false; } } if (flag) { count++; } } return count; }
但是此解法的時間複雜度太高了,是O(n^2),那就需要再優化下。
03 第二種解法
如果n可以被某個數p整除,則n = p×q,並且由於p≤q,我們可以推匯出p小於等於根號n。對正整數n,如果用2到根號n之間的所有整數去除,均無法整除,則n為質數。對於根號的處理,我們將內部迴圈換成指標的平方。
public int countPrimes2(int n) { int count = 0; for (int i = 1; i < n; i++) { if (isPrime(i)) count++; } return count; } private boolean isPrime(int num) { if (num <= 1) return false; for (int i = 2; i * i <= num; i++) { if (num % i == 0) return false; } return true; }
04 第三種解法
一個素數的倍數都不是素數。 比如2,依次往上乘,4,6,8等等,他們都不是質數,再比如3,也可以依次往上乘,得到的結果也不是質數。
我們從2開始遍歷到根號n,先找到第一個質數2,然後將其所有的倍數全部標記出來,然後到下一個質數3,標記其所有倍數,一次類推,直到根號n,此時陣列中未被標記的數字就是質數。對此我們需要使用一個長度為n的布林型別陣列,來儲存那些被標記的非質數。外層迴圈和內層迴圈都是遍歷到根號n即可。
public int countPrimes3(int n) { boolean[] isPrime = new boolean[n]; for (int i = 2; i < n; i++) { isPrime[i] = true; } for (int i = 2; i * i < n; i++) { if (!isPrime[i]) continue; for (int j = i * i; j < n; j += i) { isPrime[j] = false; } } int count = 0; for (int i = 2; i < n; i++) { if (isPrime[i]) count++; } return count; }
此解法的空間複雜度是O(n),時間複雜度是O(nlog(log n))。
05 小結
演算法專題目前已連續日更超過一個月,演算法題文章49 +篇,公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞,獲取系列文章合集。
以上就是全部內容,如果大家有什麼好的解法思路、建議或者其他問題,可以下方留言交流,點贊、留言、轉發就是對我最大的回報和支援!