LeetCode-计数质数
发布网友
发布时间：2024-10-01 12:15
共1个回答
热心网友
时间：2024-10-26 12:58
LeetCode 题目：
?  给定整数?n?，返回所有小于非负整数?n?的质数的数量。 <hr style=" border:solid; width:100px; height:1px;" color=#000000 size=1">
说明一、题目输入： n = 10输出： 4解释： 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。二、分析题目我感觉是有点儿问题的，他应该想表达的意思是求取小于给定数的所有质数的数量，并且是正整数。
我们很容易就能想到使用遍历枚举的方式进行输出，但是这样的时间复杂度过高，不太可取。
因此我们换一个思维来看题，如果我们现在拿到了一个质数，那么所有大于当前质数且存在倍数关系的数据都不是质数，下次计算到的时候就不用再判断了。
利用这样的思想就可以使用一个数组来进行标记，只要当前的标志为空，那么就是一个质数，并且要将所有的当前数的倍数给进行标记。
中间为了避免重复计算，只要一个数是已有质数的一个倍数就可以不用往后标记了，因为同一个数可能与多个质数保持倍数关系。
这种方法也有一个学名，叫做线性筛。
class Solution {public int countPrimes(int n) {List<Integer> ret = new ArrayList();int[] flag = new int[n];for(int i = 2; i < n; i++) {if(flag[i] == 0) {ret.add(i);}for(int j = 0; j < ret.size() && i * ret.get(j) < n; j++) {flag[i * ret.get(j)] = 1;if(i % ret.get(j) == 0) break;}}return ret.size();}}<hr style=" border:solid; width:100px; height:1px;" color=#000000 size=1">
总结大量数据计算下的剪枝操作。
原文：https://juejin.cn/post/7100021807926738981