統計所有小于非負整數?n?的質數的數量。
示例:
輸入: 10
輸出: 4
解釋: 小于 10 的質數一共有 4 個, 它們是 2, 3, 5, 7 。思路：篩法，見代碼。
class Solution {public int countPrimes(int n) {// 1. 給數加上標記byte[] nums = new byte[n];for (int i = 0; i < n; i++) {nums[i] = 1;}// 2. 非質數標記清除for (int i = 2; i < n; i++) {if (nums[i] == 1) {// 如果當前數為質數，篩掉倍數數字for (int j = 2; i * j < n; j++) {nums[i * j] = 0;}}}//3. 統計int count = 0;for (int i = 2; i < n; i++) {if (nums[i] == 1)count++;}return count;}
}?
