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

这篇具有很好参考价值的文章主要介绍了204. 计数质数（埃式筛法详解）——【Leetcode每日一题】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

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

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

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

1、素数分解

每一个数 都可以分解成 素数的乘积，且这种分解是唯一的，例如： $84 = 2^2 * 3^1 * 5^0 * 7^1 * 11^0 * 13^0 * 17^0 * …$

2、整除

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

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

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

$x$ 和 $y$ 的最大公约数为： $gcd(x,y) = 2^{min(m0,n0)} * 3^{min(m1,n1)} * 5^{min(m2,n2)} * ...$
```
//辗转相除法
int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}
```
$x$ 和 $y$ 的最小公倍数为： $lcm(x,y) = 2^{max(m0,n0)} * 3^{max(m1,n1)} * 5^{max(m2,n2)} * ...$
```
//最小公倍数为两数的乘积除以最大公约数。
int lcm(int a, int b) {
	return a * b / gcd(a, b);
}
```

4、使用位操作和减法求解最大公约数

对于 a 和 b 的最大公约数 f(a, b)，有：

如果 a 和 b 均为偶数，f(a, b) = 2*f(a/2, b/2);
如果 a 是偶数 b 是奇数，f(a, b) = f(a/2, b);
如果 b 是偶数 a 是奇数，f(a, b) = f(a, b/2);
如果 a 和 b 均为奇数，f(a, b) = f(b, a-b);

乘 2 和除 2 都可以转换为移位操作。

public int gcd(int a, int b) {
    if (a < b) {
        return gcd(b, a);
    }
    if (b == 0) {
        return a;
    }
    boolean isAEven = isEven(a), isBEven = isEven(b);
    if (isAEven && isBEven) {
        return 2 * gcd(a >> 1, b >> 1);
    } else if (isAEven && !isBEven) {
        return gcd(a >> 1, b);
    } else if (!isAEven && isBEven) {
        return gcd(a, b >> 1);
    } else {
        return gcd(b, a - b);
    }
}

204. 计数质数

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

示例 1：

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

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：0

提示：

$0 <= n <= 5 * 10^6$

思路：（埃式筛法）

埃式筛法

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

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

我们要筛选出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 stub
		int 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 stub
		int 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]) {//如果是素数则加入primes
				primes.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();
    }
}

运行结果：

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

复杂度分析：

埃式筛法

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

极致优化（线性筛）

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

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

题目来源：力扣。文章来源地址https://www.toymoban.com/news/detail-404311.html

到了这里，关于204. 计数质数（埃式筛法详解）——【Leetcode每日一题】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

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

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

1、素数分解

2、整除

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

4、使用位操作和减法求解最大公约数

204. 计数质数

示例 1：

示例 2：

示例 3：

提示：

思路：（埃式筛法）

埃式筛法

代码：(Java)

运行结果：

复杂度分析：

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

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2

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

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

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

1、素数分解

2、整除

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

4、使用位操作和减法求解最大公约数

204. 计数质数

示例 1：

示例 2：

示例 3：

提示：

思路：（埃式筛法）

埃式筛法

代码：(Java)

运行结果：

复杂度分析：

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

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2

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

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