204. 计数质数 （埃式筛法详解）——【Leetcode每日一题】

素数最朴素判断思路：（一般会超时）

对正整数 n，如果用 2 到 n\\sqrt{n}n​ 之间的所有整数去除，均无法整除，则 n 为素数又称为质数。

为什么到n\\sqrt{n}n​ 就可以了，因为因数如果存在一定是成对出现的，如果存在小于根号n的因数，那么n除以它一定大于根号n。

首先要先知道以下几个知识点：

1、素数分解

• 每一个数 都可以分解成 素数的乘积，且这种分解是唯一的，例如： 84=22∗31∗50∗71∗110∗130∗170∗…84 = 2^2 * 3^1 * 5^0 * 7^1 * 11^0 * 13^0 * 17^0 * …84=22∗31∗50∗71∗110∗130∗170∗…

2、整除

• 令 x=2m0∗3m1∗5m2∗7m3∗11m4∗…x = 2^{m0} * 3^{m1} * 5^{m2} * 7^{m3} * 11^{m4} * …x=2m0∗3m1∗5m2∗7m3∗11m4∗…
• 令 y=2n0∗3n1∗5n2∗7n3∗11n4∗…y = 2^{n0} * 3^{n1} * 5^{n2} * 7^{n3} * 11^{n4} * …y=2n0∗3n1∗5n2∗7n3∗11n4∗…

如果 $x$ 整除 $y$（$y$ mod $x$ == 0），则对于所有 $i$，mi<=nim^i <= n^imi<=ni。

3、最大公约数最小公倍数

• $x$ 和 $y$ 的最大公约数为：gcd(x,y)=2min(m0,n0)∗3min(m1,n1)∗5min(m2,n2)∗...gcd(x,y) = 2^{min(m0,n0)} * 3^{min(m1,n1)} * 5^{min(m2,n2)} * ...gcd(x,y)=2min(m0,n0)∗3min(m1,n1)∗5min(m2,n2)∗...

• $x$ 和 $y$ 的最小公倍数为：lcm(x,y)=2max(m0,n0)∗3max(m1,n1)∗5max(m2,n2)∗...lcm(x,y) = 2^{max(m0,n0)} * 3^{max(m1,n1)} * 5^{max(m2,n2)} * ...lcm(x,y)=2max(m0,n0)∗3max(m1,n1)∗5max(m2,n2)∗...

204. 计数质数

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

示例 1：

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

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：0

提示：

• 0<=n<=5∗1060 <= n <= 5 * 10^60<=n<=5∗106

思路：（埃式筛法）

埃式筛法

埃拉托斯特尼算法是希腊数学家埃拉托斯特尼（阿基米德的好友）发明的用来筛选素数的方法，为了方便我们一般简称为埃式筛法或者筛法。

• 埃式筛法的思路非常简单，就是用已经筛选出来的素数去过滤所有能够被它整除的数。
• 这些素数就像是筛子一样去过滤自然数，最后被筛剩下的数自然就是 不能被前面素数整除的数，根据素数的定义，这些剩下的数也是素数。

我们要筛选出n以内的所有素数:
1、我们知道2是最小的素数，我们先用2可以筛掉所有的偶数。
2、然后往后遍历到3，3是被2筛剩下的第一个数，也是素数，我们再用3去筛除所有能被3整除的数。
3、筛完之后我们继续往后遍历，第一个遇到的数是5，所以5也是素数，我们再重复以上的过程，直到遍历结束为止。
……
结束的时候，我们就获得了n以内的所有素数。

极致优化（线性筛）

• 筛法的复杂度已经非常近似$O(n)$了，因为即使在n很大的时候，经过两次ln的计算，也非常近似常数了，实际上在绝大多数使用场景当中，上面的算法已经足够应用了。
• 但是仍然有大牛不知满足，继续对算法做出了优化，将其优化到了
  的复杂度。虽然从效率上来看并没有数量级的提升，但是应用到的思想非常巧妙，值得我们学习。

比较明显地可以看出来，对于一个合数而言，它可能会被多个素数筛去。比如12，它有2和3这两个素因数，那么它就会被置为两次；

这就带来了额外的开销，如果对于每一个合数我们只更新一次，那么是不是就能优化到$O(n)$了呢？

• 这里要用到上面素数分解的定理，就是每个合数分解质因数的结果是唯一的。既然是唯一的，那么一定可以找到最小的质因数，如果我们能够保证一个合数只会被它最小的质因数更新为True，那么整个优化就完成了。

那我们具体怎么做呢？其实也不难:
1、我们假设整数n的最小质因数是m；
2、那么我们用小于m的素数i乘上n可以得到一个合数。我们将这个合数消除；
3、对于这个合数而言，i 一定是它最小的质因数。因为它等于i * n，n最小的质因数是m，i 又小于m，所以i是它最小的质因数。
……
我们用这样的方法来生成消除的合数，这样来保证每个合数只会被它最小的质因数消除。

代码：(Java)

public class CountPrimes {public static void main(String[] args) {// TODO Auto-generated method stubint n = 10;System.out.println(countPrimes(n));}public static int countPrimes(int n) {if(n <= 1) {return 0;}int count = 0; //个数boolean[] notPrimes = new boolean[n + 1]; //数组存储是否为素数for(int i = 2; i < n; i++) {if(notPrimes[i]) {continue;}count++;//i是素数//从 i * i开始（如果 k < i ，那么 k*i 在之前就已经去除过了）for(long j = (long)i * i; j < n; j += i) {notPrimes[(int) j] = true;}}return count;}
}

极致优化（线性筛）

import java.util.ArrayList;
import java.util.List;public class CountPrimes {public static void main(String[] args) {// TODO Auto-generated method stubint n = 10;System.out.println(countPrimes(n));}public static int countPrimes(int n) {if(n <= 1) {return 0;}boolean[] notPrimes = new boolean[n + 1]; List<Integer> primes = new ArrayList<Integer>();for(int i = 2; i < n; i++) {if(!notPrimes[i]) {//如果是素数则加入primesprimes.add(i);}for(int j = 0; j < primes.size() && i * primes.get(j) < n; j++) {notPrimes[i * primes.get(j)] = true;if(i % primes.get(j) == 0) {// 到 合数i 的最小质数时，停止break;}}}return primes.size();}
}

运行结果：

复杂度分析：

埃式筛法

• 时间复杂度：$O(n\ast lnln(n))$，我们一共有了两层循环，最外面一层循环固定是遍历n次。而里面的这一层循环遍历的次数一直在变化，并且它的运算次数和素数的大小相关，看起来似乎不太方便计算。实际上是可以的，根据素数分布定理以及一系列复杂的运算.
• 空间复杂度：$O(n)$，需要开辟长度为n的数组，n为给定的整数

极致优化（线性筛）

• 时间复杂度：$O(n)$，赋值的次数减少了.
• 空间复杂度：$O(n)$.

注：仅供学习参考， 如有不足，欢迎指正！

题目来源：力扣。