/**
Given an integer n, return the number of prime numbers that are strictly less
than n.
Example 1:
Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
Example 2:
Input: n = 0
Output: 0
Example 3:
Input: n = 1
Output: 0
Constraints:
0 <= n <= 5 * 10⁶
Related Topics数组 | 数学 | 枚举 | 数论
👍 977, 👎 0
*/
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int countPrimes(int n) {
boolean[] primes = new boolean[n];
int end = n % 2 == 0 ? n / 2 : (n + 2) / 2;
for (int i = 2; i <= end; i++) {
for (int j = 2; j <= end; j++) {
int num = i * j;
if (num > n) {
break;
}
primes[num - 1] = true;
}
}
int result = 0;
for (int i = 1; i < n - 1; i++) {
if (!primes[i]) {
result++;
}
}
return result;
}
}
//leetcode submit region end(Prohibit modification and deletion)
