一、題目大意
https://leetcode.cn/problems/count-primes
給定整數 n ，回傳 所有小于非負整數 n 的質數的數量 ，
示例 1：
輸入：n = 10
輸出：4
解釋：小于 10 的質數一共有 4 個, 它們是 2, 3, 5, 7 ，
示例 2：
輸入：n = 0
輸出：0
示例 3：
輸入：n = 1
輸出：0
提示：
- 0 <= n <= 5 * 106
二、解題思路
輸入一個整數，輸出也是一個整數，表示小于輸入數的質數的個數，
埃拉托斯特尼篩法，是判斷一個整數是否是質數的方法，并且它可以在判斷一個整數n時，同時判斷所小于n的整數，因此非常適合這個問題，其原理是：從1到n遍歷，假設當前遍歷到m，則把所有小于n的、且是m的倍數的整數標為和數；遍歷完成后，沒有被標為和數的數字即為質數，
三、解題方法
3.1 Java實作
public class Solution {
public int countPrimes(int n) {
if (n <= 2) {
return 0;
}
boolean[] prime = new boolean[n];
Arrays.fill(prime, true);
int i = 3;
int sqrtn = (int) Math.sqrt(n);
// 偶數一定不是質數
int count = n / 2;
while (i <= sqrtn) {
// 最小質因子一定小于等于開方數
for (int j = i * i; j < n; j += 2 * i) {
// 避免偶數和重復遍歷
if (prime[j]) {
count--;
prime[j] = false;
}
}
do {
i+= 2;
// 避免偶數和重復遍歷
} while (i <= sqrtn && !prime[i]);
}
return count;
}
}
四、總結小記
- 2022/8/1 7月結束了貪心演算法的題，開啟“巧解數學問題”類的題目
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/500765.html
標籤：其他