数论——欧拉筛、埃氏筛
记录一点关于数论的知识，该知识点本身不难，主要是学习一下思想~
埃氏筛
埃拉托斯特尼筛法，简称埃氏筛。
一个质数的倍数一定是合数，所以，假设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]); } } }
总结
素数筛法的思想仍然是通过已有条件筛出能够事先拿出的答案，从而达到优化的效果，其思想值得我们学习!
文章粗浅，希望对大家有帮助！
