LEETCODE，[LeetCode] 204. Count Primes

204.?Count Primes

---

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

Example:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.


題意：找素數，找n以內有多少個素數
篩數法統計

class Solution {public int countPrimes(int n){if (n == 0 || n == 1 || n == 2)return 0;int[] num = new int [n];for (int i = 0; i < n; i++) {num[i] = i;}for (int i = 2; i < n; i++) {if (num[i] != 0) {for (int j = 2; j*i < n; j ++)num[j*i] = 0;}}int sum = 0;for (int i = 0; i < n; i++) {if (num[i] != 0)sum ++;}return sum - 1;}
}

最快的算法應該是 6n那個，但是我不會，hhaha有興趣的小伙伴可以自學一下