【数论】 质数

一、质数定义

质数（英文名：Prime number）又称素数，是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。否则称为合数（规定1既不是质数也不是合数）。

二、试除法判定质数

给定 n 个正整数 $a_i$，判定每个数是否是质数。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个正整数 $a_i$。

输出格式

共 n 行，其中第 ii 行输出第 ii 个正整数 $a_i$ 是否为质数，是则输出 Yes，否则输出 No。

数据范围

1≤n≤100,
1≤$a_i$≤$2^{31}-1$

输入样例：

2
2
6

输出样例：

Yes
No

【思路分析】

通过最朴素的想法，我们只需要枚举从2开始到n -1 之间的所有数，判断该数n是否被其中一项整除，如果被整除，那么该数n就不是质数

public static boolean isPrime(int n) {
    if(n < 2) {
        return false;
    }
    for(int i = 2; i <= n; i++) {
        if(n % i == 0) {
            return false;
        }
    }
    return true;
}

那么是否可以优化呢？我们都知道能够整除n的因数都是成对出现的，比如12 能够被3和4整除，求中必然有一个大于$\sqrt{n}$ 一个小于$\sqrt{n}$

，很好反证，如果两个数都大于$\sqrt{n}$，那么这俩数相乘的结果将会大于n

所以没必要枚举2到n - 1所有数，只需要枚举到$\sqrt{n}$即可

public static boolean isPrime(int n) {
    if(n < 2) {
        return false;
    }
    for(int i = 2; i <= n / i; i++) {
        if(n % i == 0) {
            return false;
        }
    }
    return true;
}

值得注意的是，为什么表示 i <= Math.sqrt(n) 时不直接调用函数，或者写成i * i <= n呢

第一点就是调用Math.sqrt()函数会在每次循环中都计算一次，第二点就是i * i可能会超过数据类型的最大值

上题完整代码

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        while(m-- > 0) {
            if (isPrime(sc.nextInt())){
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
        sc.close();
    }
    public static boolean isPrime(int n) {
        if(n < 2) {
            return false;
        }
        for(int i = 2; i <= n / i; i++) {
            if(n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

三、分解质因数

我们都知道，一个合数能够写成若干个质因数的乘积，例如 18 = 2×3×3，2 和 3 是 18 的质因数。

因此基于质因数分解的基本原理，通过不断将 n 除以其最小的质因数，直到 n 变为 1

【例题】

给定 n 个正整数 $a_i$，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个正整数 $a_i$。

输出格式

对于每个正整数 $a_i$，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。

每个正整数的质因数全部输出完毕后，输出一个空行。

数据范围

1≤n≤100,
2≤ai≤2×$10^9$

输入样例：

2
6
8

输出样例：

2 1
3 1

2 3

【解答】

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 创建一个Scanner对象，用于从标准输入读取数据
        Scanner sc = new Scanner(System.in);
        // 读取一个整数m，表示接下来要输入的整数的个数
        int m = sc.nextInt();
        // 循环m次，每次读取一个整数并调用printAllPrimeFactor方法进行质因数分解
        while(m-- > 0) {
            printAllPrimeFactor(sc.nextInt());
        }
        // 关闭Scanner对象，释放资源
        sc.close();
    }

    public static void printAllPrimeFactor(int n) {
        // 从最小的质数2开始枚举，直到根号n
        for(int i = 2; i <= n / i; i++) {
            // 这里i一定是质数，因为包含2 ~ i - 1这个因子的数被除掉了
            if(n % i == 0) {
                // 记录当前质因数i出现的次数
                int num = 0;
                // 不断将n除以i，直到n不能再被i整除
                while(n % i == 0) {
                    num ++;
                    n /= i;
                }
                // 输出当前质因数i及其出现的次数
                System.out.println(i + " " + num);
            }
        }
        // 出循环进行判断，因为上面循环仅枚举到了根号n，一个数至多有一个大于根号n的质因子
        if(n > 1) {
            // 对剩下的这个单独质因子进行处理
            System.out.println(n + " 1");
            System.out.println();
        } else {
            System.out.println();
        }
    }
}

四、筛质数

对于筛质数，这里仅介绍一种埃式筛法

给定一个正整数 n，请你求出1∼n 中质数的个数。

首先将 2 到 n 范围内的整数写下来。其中 2 是最小的素数。将表中所有的 2 的倍数划去，表中剩下的最小的数字就是 3，它不能被更小的数整除，所以 3 是素数。再将表中所有的 3 的倍数划去…… 以此类推，如果表中剩余的最小的数是 m，那么 m 就是素数。然后将表中所有 m 的倍数划去，像这样反复操作，就能依次枚举 n 以内的素数。

以下是用上述方法枚举 2 - 20 之间素数的具体过程：

1. 初始化：列出 2 - 20 的所有整数：2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20 。

2. 筛选过程

   • 第一步：2 是最小的素数，划去所有 2 的倍数（4、6、8、10、12、14、16、18、20 ），此时剩下的数为：2、3、5、7、9、11、13、15、17、19 。
   • 第二步：在剩下的数中，3 是最小的数，且不能被更小的数整除，所以 3 是素数。划去所有 3 的倍数（9、15 ），此时剩下的数为：2、3、5、7、11、13、17、19 。
   • 第三步：在剩下的数中，5 是最小的数，且不能被更小的数整除，所以 5 是素数。划去所有 5 的倍数，2 - 20 中 5 的其他倍数已在前面步骤被划去，剩下的数不变，仍为 2、3、5、7、11、13、17、19 。
   • 第四步：在剩下的数中，7 是最小的数，且不能被更小的数整除，所以 7 是素数。划去所有 7 的倍数（2 - 20 中 7 的倍数 14 已在前面被划去） ，剩下的数还是 2、3、5、7、11、13、17、19 。
   • 第五步及以后：随着继续考察剩下数中的最小数（11、13、17、19 ），它们都不能被更小的数整除，都是素数，且 2 - 20 中它们的倍数都已在前面步骤被处理过，没有新的数可划去。

3. 结果：经过上述操作，2 - 20 之间剩下的数 2、3、5、7、11、13、17、19 就是该范围内的素数。 这种方法叫埃拉托斯特尼筛法，通过不断划去素数的倍数，能高效找出一定范围内的素数。

【例题】

给定一个正整数 n，请你求出 1∼n 中质数的个数。

输入格式

共一行，包含整数 n。

输出格式

共一行，包含一个整数，表示 1∼n 中质数的个数。

数据范围

1≤n≤$10^6$

输入样例：

8

输出样例：

4

【解答】

import java.io.*;
import java.util.*;
public class Main {
    static final int N = 1000010;
    static int prime[] = new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int res = function(sc.nextInt());
        System.out.println(res);
        sc.close();
    }
    public static int function(int n) {
        int ans = 0;
        for(int i = 2; i<= n; i++) {
            if(prime[i] == 0) {
                for(int j = 2 * i; j <= n; j += i) {
                    prime[j] = 1;
                }
            }
            if(prime[i] == 0) {
                ans++;
            }
        }
        return ans;
    }
}