欧拉筛&&埃氏筛

向右看齐 2024-03-30 12:54 100阅读 0赞

## 数论——欧拉筛、埃氏筛 ##

`记录一点关于数论的知识，该知识点本身不难，主要是学习一下思想~`

--------------------

#### 文章目录 ####

*  数论——欧拉筛、埃氏筛
 *  埃氏筛
 *  欧拉筛
 *  总结

--------------------

## 埃氏筛 ##

> 埃拉托斯特尼筛法，简称埃氏筛。  
> 一个质数的倍数一定是合数，所以，假设P PP是质数，我们可以筛掉区间\[ 1 , 1 e 7 \] 中所有P的倍数。  
> 对于数列1~11：  
> 先筛去2的倍数（4、6、8、10），然后筛去3的倍数（6、9），然后筛去5的倍数（10）。  
> 至此，1~11内的所有合数都被筛完了， 2 3 5 7 11是数列中的质数。  
> 为什么这样能筛去所有的合数呢，因为一个合数一定能被分解为几个质数的幂的乘积，并且这个数的质因子一定是小于它本身的，所以当我们从小到大将每个质数的倍数都筛去的话，当遍历到一个合数时，它一定已经被它的质因子给筛去了。  
> 但筛除3的倍数时，我们还是从3的2倍开始筛，其实3 \* 2 ，已经被2 \* 3时筛过了。  
> 所以我们每一次只需要从i\*i开始筛！此时时间复杂度可以近似看成O ( n )了。

**埃氏筛代码：**

public class 数论_埃氏筛 {
        
        static final int N = (int) (1e7 + 5);
        static int[] st = new int[N];
    
        public static void E_sieve(int n) {
        
            for (int i = 2; i <= n / i; i++)
                if (st[i] == 0)
                    for (int j = i * i; j <= n; j += i)
                        st[j] = 1; // j是i的一个倍数，j是合数，筛掉。
        }
    
    }

## 欧拉筛 ##

> 埃氏筛是筛去每个质数的倍数，但难免，会有合数会被其不同的质因子多次重复筛去。这就造成了时间浪费。  
> 所以，我们不需要用一个for循环去筛除一个质数的所有倍数，我们将所有质数存储到primes\[\]中，然后枚举到第i个数时，就筛去所有的primes\[j\] \* i。这样就在每一次遍历中，正好筛除了所有已知素数的i倍。  
> 但是为了确保合数只被最小质因子筛掉，最小质因子要乘以最大的倍数，即要乘以最大的i , 所以不能提前筛，所以如果 i % primes \[ j \] = = 0 , 我们就结束内层循环！

**欧拉筛代码：**

public class 数论_欧拉筛 {
        
        static final int N = (int) (1e7 + 5);
        static int cnt = 0;
        static int[] st = new int[N], primes = new int[N];
    
    
        static void ola(int n) {
        
            for (int i = 2; i <= n; i++) {
        
                if (st[i] == 0)
                    primes[cnt++] = i;//将质数存到primes中
                for (int j = 0; primes[j] <= n / i; j++) {
        //要确保质数的第i倍是小于等于n的。
                    st[primes[j] * i] = 1;
                    if (i % primes[j] == 0)
                        break;//欧拉筛的核心思想就是确保每个合数只被最小质因数筛掉。或者说是被合数的最大因子筛掉。
                }
            }
        }
    
        public static void main(String[] args) {
        
            ola(8);
            for (int i = 0; i < cnt; i++) {
        
                System.out.println(primes[i]);
            }
        }
    }

--------------------

## 总结 ##

`素数筛法的思想仍然是通过已有条件筛出能够事先拿出的答案，从而达到优化的效果，其思想值得我们学习!`

文章粗浅，希望对大家有帮助！

*参考博客：[素数筛法详解：埃氏筛和欧拉筛][Link 1]*

[Link 1]: https://blog.csdn.net/GD_ONE/article/details/104660294