数论——欧拉筛、埃氏筛

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

文章目录

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

埃氏筛

埃拉托斯特尼筛法，简称埃氏筛。
一个质数的倍数一定是合数，所以，假设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]);
        }
    }
}