204. Count Primes

题目描述和难度

  • 题目描述:

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

示例:

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

思路分析

求解关键:

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

参考解答

参考解答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