LeetCode 质数计数（厄拉多塞筛法）

zhichangterry 发布于2021-11-15 11:38 / 2976人阅读

摘要：问题统计所有小于非负整数的质数的数量。示例输入输出解释小于的质数一共有个它们是。优化做法厄拉多塞筛法算法详解及图片展示代码

问题：

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

示例：

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

优化做法：
厄拉多塞筛法：
算法详解及图片展示

代码：

public static int countPrime(int n){        int count = 0;        boolean[] signs = new boolean[n];        for (int i = 0; i < n;i++){            signs[i] = true;        }        for (int i = 2; i < n; i++){            if(signs[i]) {                count++;                for (int j = i + i ; j < n ;j += i){                    signs[j] = false;                }            }        }        return count;    }

云服务器 GPU云服务器筛法求 LeetCode 拉多 LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/123344.html

小李飞刀：做题第八弹！

摘要：认真做题的分割线第一题乘积最大子序列难度中等给定一个整数数组，找出一个序列中乘积最大的连续子序列该序列至少包含一个数。写在前面的话慢慢转变思路，不再死磕不会做的题，思路可以先借鉴，但是一定要吃透透。上周末看完看完了《算法图解》，感觉对一些题目的思路有比较大的帮助，但是还是要在实践中理解。认真做题的分割线第一题 152. 乘积最大子序列难度：中等给定一个整数数组nums，找出一个...

ztyzz 2019-07-31 10:11 评论0 收藏0
LeetCode 204 线性筛计数质数

摘要：存放所有数据，默认全部为素数存放素数，这是有序的，从小到大。如可由或所得，我们只取最小素因子即可假设整数为另一个乘数由如下面我们排除了是一个正整数所以，若能被整除也能被整除 static public int CountPrimes(int n) { //buf 存放所有数据，默认全部为...

不知名网友 2021-11-30 14:52 评论0 收藏0
[LeetCode] Count Primes

摘要：用数组标记非质数，每当出现一个为，计数器加一。关于质数有三点大于的质数一定是奇数，如，，奇数中的非质数也一定是奇数的乘积。首先，我们用从到进行标记。标记完所有的合数之后，再用到之间的遍历，所有未被标记的质数。 Problem Count the number of prime numbers less than a non-negative number, n. Note 用数组fla...

Shisui 2019-08-14 15:54 评论0 收藏0
Leetcode PHP题解--D57 762. Prime Number of Set Bits

摘要：题目链接题目分析对给定范围内的每个整数，返回其二进制形式下，数字出现的次数为质数的次数。思路由于题目固定了范围为，次方为千万。即最多只会出现次。存在则符合题目要求的数字，否则不计入该数字。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 D57 762. Prime Number of Set Bits in Binary Representation 题目链接 762. Prime ...

Cobub 2019-07-01 12:45 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月汇总（55 题攻略）

摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目录不...

warmcheng 2019-08-26 10:09 评论0 收藏0