868. 筛质数

给定一个正整数 n，请你求出 1∼n 中质数的个数。
输入格式
共一行，包含整数 n。
输出格式
共一行，包含一个整数，表示 1∼n 中质数的个数。
数据范围
1≤n≤106
输入样例：

  1. 8

输出样例：

  1. 4

朴素做法

for循环 2~n ，
判断当前数是不是合数，不是的话把他加入素数集合中
for循环将当前数的倍数都断定为合数

时间复杂度： O(nlogn) 

  1. import java.util.*;
  3. public class Main {
  5.     public static void main(String[] args) {
  6.         Scanner sc = new Scanner(System.in);
  8.         int n = sc.nextInt();
  10.         int res = getPrimers(n);
  12.         System.out.println(res);
  13.     }
  15.     static int getPrimers(int n) {
  16.         boolean[] st = new boolean[n + 1];
  17.         //这个数组其实有没有都行，因为目的是求质数个数，不是每个质数
  18.         //后面的线性筛法需要，所以保留一下
  19.         int[] primers = new int[n];
  20.         int idx = 0;
  22.         for (int i = 2; i <= n; i++) {
  23.             //判断当前数是否为素数
  24.             if (!st[i]) primers[idx++] = i;
  26.             //用当前数更新后面的数
  27.             for (int j = i; j <= n; j += i) {
  28.                 st[j] = true;
  29.             }
  30.         }
  32.         return idx;
  33.     }
  34. }

埃氏筛法

相较于线性筛法，将内层for循环放入if内，意思是只用质因子更新后面的合数。
这也很好理解，因为一个合数必然能被分解为质因子的乘积。

时间复杂度： O(nloglogn) 

  1. import java.util.*;
  3. public class Main {
  5.     public static void main(String[] args) {
  6.         Scanner sc = new Scanner(System.in);
  8.         int n = sc.nextInt();
  10.         int res = getPrimers(n);
  12.         System.out.println(res);
  13.     }
  15.     static int getPrimers(int n) {
  16.         boolean[] st = new boolean[n + 1];
  17.         int[] primers = new int[n];
  18.         int idx = 0;
  20.         for (int i = 2; i <= n; i++) {
  21.             //判断当前数是否为素数
  22.             if (!st[i]) {
  23.                 primers[idx++] = i;
  24.                 //用素数更新后面的数
  25.                 for (int j = i; j <= n; j += i) {
  26.                     st[j] = true;
  27.                 }
  28.             }
  30.         }      
  31.         return idx;
  32.     }
  33. }

线性筛法

相较于埃氏筛法又有了改进。
对于埃氏筛法来说，有的合数会被筛多次，例如：求1-100中的质数，对于12来说，当i遍历到2时st[12]被置为true，当i遍历到3时，st[12]又被置为true。也就是说一个合数会被所有比它小的质因子都筛一遍。

线性筛法的原理就是每个合数都是被它的最小质因子筛掉的
时间复杂度O(n)

  1. import java.util.*;
  3. public class Main {
  5.     public static void main(String[] args) {
  6.         Scanner sc = new Scanner(System.in);
  8.         int n = sc.nextInt();
  10.         int res = getPrimers(n);
  12.         System.out.println(res);
  13.     }
  15.     static int getPrimers(int n) {
  16.         boolean[] st = new boolean[n + 1];
  17.         int[] primers = new int[n];
  18.         int idx = 0;
  20.         for (int i = 2; i <= n; i++) {
  21.             //判断当前数是否为素数
  22.             if (!st[i]) primers[idx++] = i;
  24.             for (int j = 0; primers[j] <= n / i; j++) {
  25.                 //当i % primers[j] != 0时primers[j]与i互质，i*primers[j]的最小质因子就是primers[j]
  26.                 st[primers[j] * i] = true;    
  27.                 //当i % primers[j] == 0 时，
  28.                 //i的最小质因子是primers[j]，所以i*primers[j]的最小质因子就是primers[j]
  29.                 if (i % primers[j] == 0) break;
  30.             }
  32.         }
  34.         return idx;
  35.     }
  36. }
  1. // 20220405 新版代码

几个问题

  1. 内层if一定能使内层for循环结束吗？

答：一定能。因为primers数组存储了 2~i 之间的所有质因子
如果i是质数，一定能结束，因为primers数组当前的最后一个质数就是i， i % i == 0
如果i是合数，也一定能结束，因为i能被分解为质数的乘积且这些质数一定小于i，由于primers中已经存储了 2~i 的所有质数，当 primers[j] 为i的最小质因子时 i % primers[j] == 0

  1. 合数一定都会被筛掉吗？

答：一定会。因为合数能分解为质数的乘积，考虑这样一种分解，对于合数k，假定它的最小质因子为a，那么它的另一个质因子 b = k / a 。
外层循环i的范围是 2~n ，包含了所有b的范围，也就是说，只要我们能找到k的最小质因子a，就可以筛掉 k = a * b
如果当前i是质数，i一定会被存入 primers 数组的当前最后一个位置上。只要 primers[j] * i <= n，就能筛掉一个合数
如果当前i是合数，i的最小质因子一定在primers中，当 i % primer[j] == 0 时说明当前i的最小质因子就是primers[j]，那么对于 i * primers[j] 来说，它的最小质因子还是primers[j] ，应该被筛掉。且此时应退出内层循环，不能再继续筛，因为此时 i * primers[j] 不是被primers[j]筛掉的，而是被i的最小质因子筛掉的

应用

:::tips 如果题目要求对多个数字进行算术基本定理分解，可以考虑结合线性筛进行快速计算 :::

AcWing 1295. X的因子链

  1. import java.util.*;
  3. public class Main {
  4.     static int N = (1 << 20) + 10;
  5.     static int[] primers = new int[N], minp = new int[N];
  6.     static boolean[] st = new boolean[N];
  7.     static int cnt;
  8.     public static void main(String[] args) {
  9.         Scanner sc = new Scanner(System.in);
  10.         get_primers(N - 1);
  11.         while (sc.hasNext()) {
  12.             int x = sc.nextInt();
  13.             deal(x);
  14.         }
  15.     }
  17.     static void deal(int x) {
  18.         int[] c = new int[30];
  19.         int tot = 0, idx = 0;
  20.         while (x > 1) {
  21.             int k = minp[x], cc = 0;
  22.             while (x % k == 0) {
  23.                 cc++;
  24.                 tot++;
  25.                 x /= k;
  26.             }
  27.             c[idx++] = cc;
  28.         }
  30.         long res = 1;
  31.         for (int i = 1; i <= tot; i++)
  32.             res *= i;
  34.         for (int i = 0; i < idx; i++) {
  35.             for (int j = 1; j <= c[i]; j++)
  36.                 res /= j;
  37.         }
  38.         System.out.println(tot + " " + res);
  39.     }
  41.     static void get_primers(int n) {
  42.         for (int i = 2; i <= n; i++) {
  43.             if (!st[i]) {
  44.                 minp[i] = i;
  45.                 primers[cnt++] = i;
  46.             }
  48.             for (int j = 0; primers[j] * i <= n; j++) {
  49.                 st[primers[j] * i] = true;
  50.                 minp[primers[j] * i] = primers[j];
  51.                 if (i % primers[j] == 0) break;
  52.             }
  53.         }
  54.     }
  55. }

AcWing 196. 质数距离

思路：
直接用线性筛会爆空间，爆时间
考虑到左右边界之间相差只有106，想要快速找出这一段区间内的质数，有一个Trick
如果一个数x是合数，一定存在一个小于等于sqrt(x)的质数是它的因子。
故可以考虑用线性筛法预处理50000以内的所有质数
对于一段给定区间，用50000以内的素数快速判断区间中的每个数是不是合数
总的时间复杂度包括预处理 + 求一段区间内的质数
前者为线性，后者可以类比埃氏筛法的时间复杂度，基本是线性
故总时间复杂度为线性

实现时需要考虑溢出问题！以及1不是素数！