import java.util.Arrays; /** * <p>给定整数 <code>n</code> ,返回 <em>所有小于非负整数 <code>n</code> 的质数的数量</em> 。</p> * * <p> </p> * * <p><strong>示例 1:</strong></p> * * <pre> * <strong>输入:</strong>n = 10 * <strong>输出:</strong>4 * <strong>解释:</strong>小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。 * </pre> * * <p><strong>示例 2:</strong></p> * * <pre> * <strong>输入:</strong>n = 0 * <strong>输出:</strong>0 * </pre> * * <p><strong>示例 3:</strong></p> * * <pre> * <strong>输入:</strong>n = 1 * <strong>输出</strong>:0 * </pre> * * <p> </p> * * <p><strong>提示:</strong></p> * * <ul> * <li><code>0 <= n <= 5 * 10<sup>6</sup></code></li> * </ul> * <div><div>Related Topics</div><div><li>数组</li><li>数学</li><li>枚举</li><li>数论</li></div></div><br><div><li>👍 929</li><li>👎 0</li></div> */ //leetcode submit region begin(Prohibit modification and deletion) class Solution { //避免全部扫描 // 12 = 2 × 6 //12 = 3 × 4 //12 = sqrt(12) × sqrt(12) //12 = 4 × 3 //12 = 6 × 2 public int countPrimes(int n) { boolean[] isPrimes = new boolean[n + 1]; Arrays.fill(isPrimes, true); for (int i = 2; i < n; i++) { if (isPrimes[i]) { for (int j = 2 * i; j <= n; j += i) { isPrimes[j] = false; } } } int count = 0; for (int i = 2; i < n; i++) { if (isPrimes[i]) { count++; } } return count; } } //leetcode submit region end(Prohibit modification and deletion)
不会,我可以学;落后,我可以追赶;跌倒,我可以站起来!