LeetCode 题解之 204. Count Primes

204. Count Primes

题目描述和难度

• 题目描述：

统计所有小于非负整数 n 的质数的数量。

示例:

输入: 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 ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 [email protected] 。

.label-warning {
background-color: #f0ad4e;
}

.label-success {
    background-color: #5cb85c;
}

.label-danger {
    background-color: #d9534f;
}

.label {
    display: inline;
    padding: .2em .6em .3em;
    font-size: 75%;
    font-weight: 700;
    line-height: 1;
    color: #fff;
    text-align: center;
    white-space: nowrap;
    vertical-align: baseline;
    border-radius: .25em;
}