算法记录

LeetCode 题目：

 &emsp;&emsp;给定整数 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