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

向右看齐 2024-03-24 08:26 44阅读 0赞

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

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

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

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

##### 1、素数分解 #####

*  **每一个数** 都可以分解成 **素数的乘积**，且这种分解是**唯一**的，例如：  84 = 2 2 ∗ 3 1 ∗ 5 0 ∗ 7 1 ∗ 1 1 0 ∗ 1 3 0 ∗ 1 7 0 ∗ … 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 = 2 m 0 ∗ 3 m 1 ∗ 5 m 2 ∗ 7 m 3 ∗ 1 1 m 4 ∗ … x = 2^\{m0\} \* 3^\{m1\} \* 5^\{m2\} \* 7^\{m3\} \* 11^\{m4\} \* … x=2m0∗3m1∗5m2∗7m3∗11m4∗…
 *  令  y = 2 n 0 ∗ 3 n 1 ∗ 5 n 2 ∗ 7 n 3 ∗ 1 1 n 4 ∗ … y = 2^\{n0\} \* 3^\{n1\} \* 5^\{n2\} \* 7^\{n3\} \* 11^\{n4\} \* … y=2n0∗3n1∗5n2∗7n3∗11n4∗…

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

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

*   x x x 和  y y y 的**最大公约数**为： g c d ( x , y ) = 2 m i n ( m 0 , n 0 ) ∗ 3 m i n ( m 1 , n 1 ) ∗ 5 m i n ( m 2 , n 2 ) ∗ . . . 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)∗...
    
        //辗转相除法
        int gcd(int a, int b) {
        	return b == 0 ? a : gcd(b, a % b);
        }
 *   x x x 和  y y y 的**最小公倍数**为： l c m ( x , y ) = 2 m a x ( m 0 , n 0 ) ∗ 3 m a x ( m 1 , n 1 ) ∗ 5 m a x ( m 2 , n 2 ) ∗ . . . 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)∗...
    
        //最小公倍数为两数的乘积除以最大公约数。
        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 ∗ 1 0 6 0 <= n <= 5 \* 10^6 0<=n<=5∗106

#### 思路：（埃式筛法） ####

#### 埃式筛法 ####

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

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

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

**极致优化**（线性筛）

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

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

这就带来了额外的开销，如果对于每一个合数我们只更新一次，那么是不是就能优化到 O ( n ) O(n) 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();
        }
    }

##### 运行结果： #####

![在这里插入图片描述][808e4e4434874f459950e6d46b3a9c50.png]

##### 复杂度分析： #####

**埃式筛法**

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

**极致优化**（线性筛）

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

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

题目来源：[力扣。][Link 1]

[808e4e4434874f459950e6d46b3a9c50.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/31fdd4940e3948f0a900090ba9055a53.png
[Link 1]: https://leetcode.cn/problems/count-primes/description/