204. Count Primes

题目描述和难度

• 题目描述：

输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

• 题目难度：简单。
• 英文网址：204. Count Primes 。
• 中文网址：204. 计数质数 。

思路分析

求解关键：

“埃拉托斯特尼筛法”，也称“素数筛选法”，是得到素数表的一个经典方法。

参考解答

参考解答1

import java.util.Arrays;

public class Solution3 {

    public int countPrimes(int n) {
        boolean[] primes = new boolean[n];
        Arrays.fill(primes, true);
        for (int i = 2; i < n; i++) {
            // 每一轮第一个没有被划去的数肯定是质数
            if (primes[i]) {
                for (int j = i + i; j < n; j += i) {
                    primes[j] = false;
                }
            }
        }
        // 下面开始计数
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (primes[i]) {
                count++;
            }
        }
        return count;
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0204-count-primes ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。