线性筛（欧拉筛）

1、原理

1. ✨任何一个合数（非素数）可以分解成若干个素数的积

例如：20 = 2 * 2 * 5

1. 既然一个合数一定是某些素数的积，那么我们只要把给定范围内所有素数的倍数全部筛掉，那么就只剩下素数了。

   例如：在10以内，把2的倍数（4,6,8），3的倍数（6,9），5的倍数（10）筛掉，就只剩下了（2,3,5,7）

2. 每一个数的素数因子有多个，如上例的 2、2、5，为了达到线性的复杂度，就必须唯一标识任何一个数，简单的说，每个数只能被计算出来一次。

   例如：20 既可以看做2的倍数： 2 * 10 ，又可以看做5的倍数： 5 * 4，那么20就被计算了两次，也就是被重复筛掉了两次。当这个数够大的时候，它有更多的素数因子，也就会被更多的重复筛除。

   为了唯一标识一个合数（那一串素数因子），就得找到它们的唯一特点，例如最小值或最大值。而我们筛的过程是从小到大的，那么选择最小值是最方便的。

看了这么多字还是建议直接看代码方便：

2、代码

int num = 1000; // 给定范围，这里举例为1000以内
int count = 0; // 已经筛出来的素数个数
int[] prime = new int[num]; // 素数数组
int[] check = new int[num]; // 范围内所有数是否为素数的判断数组，0表示素数，1表示合数，初始全为0
for (int i = 2; i < num; i++) {
    // i 表示的是当前需要筛的数，所以范围是2~num
    if (0 == check[i]) {
        prime[count++] = i;
    }
    // i 同时作为倍率，与所有素数相乘。所以要保证 i * prime[j] < num
    for (int j = 0; j < count && i * prime[j] < num; j++) {
        // 素数的倍数是合数
        check[i * prime[j]] = 1;
        // 如果倍率i可以被当前素数整除，那么i与后面的素数相乘时，那个素数一定不是最小因子
        if (0 == i % prime[j]) {
            break;
        }
    }
}

相信最难理解的就是这一段了

// i 同时作为倍率，与所有素数相乘。所以要保证 i * prime[j] < num
for (int j = 0; j < count && i * prime[j] < num; j++) {
    // 素数的倍数是合数
    check[i * prime[j]] = 1;
    // 如果倍率i可以被当前素数整除，那么i与后面的素数相乘时，那个素数一定不是最小因子
    if (0 == i % prime[j]) {
        break;
    }
}

1. i作为倍率，与所有素数（prime数组）相乘，应该不难理解，只是和一般的思路相反，一般来说固定的是因子，变化的是倍率：2 * 2, 2 * 3, 2 * 4。而这里固定的是倍率，变化的是因子。

2. 为什么0 == i % prime[j]时要退出，既然固定了倍率，那不是后面的素数就永远乘不到这个倍率了吗？

   • 首先明白一点，prime数组是递增的

   • 当`0 == i % prime[j]时，说明i是prime[j]的倍数，一定大于等于prime[j]，也大于前面几个素数。这可以保证，在 a * b 的形式中，前面几个素数永远是小的那个因子。

   • 这时候退出，就实现了上面原理中所说的只计算最小因子。而后面的素数与这个倍率的积，并不会被忽略，只是被分配给了最小的因子。

     例如：当i等于4时，只会与2相乘，不会筛掉3 * 4 = 12的12。这个12是被分配给了最小因子2，即2 * (2 * 3) = 12，这时i = 6

3、应用

线性筛算法并不只能用来筛素数。看了代码可以理解到，这个算法本质上是筛除了素数因子的倍数。

所以也可以应用于给定几个因子，求不被整除的数的个数这种场景。