leetcode 204. Count Primes 计数质数 (Easy)

作者：okokabcd

2022 年 8 月 01 日
本文字数：722 字
阅读完需：约 2 分钟

一、题目大意

https://leetcode.cn/problems/count-primes

给定整数 n ，返回所有小于非负整数 n 的质数的数量。

示例 1：

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

示例 2：

输入：n = 0 输出：0

示例 3：

输入：n = 1 输出：0

提示：

0 <= n <= 5 * 106

二、解题思路

输入一个整数，输出也是一个整数，表示小于输入数的质数的个数。埃拉托斯特尼筛法，是判断一个整数是否是质数的方法。并且它可以在判断一个整数 n 时，同时判断所小于 n 的整数，因此非常适合这个问题。其原理是：从 1 到 n 遍历，假设当前遍历到 m，则把所有小于 n 的、且是 m 的倍数的整数标为和数；遍历完成后，没有被标为和数的数字即为质数。

三、解题方法

3.1 Java 实现

public class Solution {    public int countPrimes(int n) {        if (n <= 2) {            return 0;        }        boolean[] prime = new boolean[n];        Arrays.fill(prime, true);
        int i = 3;        int sqrtn = (int) Math.sqrt(n);        // 偶数一定不是质数        int count = n / 2;        while (i <= sqrtn) {            // 最小质因子一定小于等于开方数            for (int j = i * i; j < n; j += 2 * i) {                // 避免偶数和重复遍历                if (prime[j]) {                    count--;                    prime[j] = false;                }            }            do {                i+= 2;                // 避免偶数和重复遍历            } while (i <= sqrtn && !prime[i]);        }        return count;    }}

复制代码

四、总结小记

2022/8/1 7 月结束了贪心算法的题，开启“巧解数学问题”类的题目

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/8cafbe2fad515cf092ef1d5be】。文章转载请联系作者。

okokabcd

关注

还未添加个人签名 2019.11.15 加入

一年当十年用的Java程序员

发布

暂无评论

创作场景