一、质数定义
质数（英文名：Prime number）又称素数，是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。否则称为合数（规定1既不是质数也不是合数）。
二、试除法判定质数
给定 n 个正整数 a i a_i ai，判定每个数是否是质数。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个正整数 a i a_i ai。
输出格式
共 n 行，其中第 ii 行输出第 ii 个正整数 a i a_i ai 是否为质数，是则输出 Yes，否则输出 No。
数据范围
1≤n≤100,
1≤ a i a_i ai≤ 2 31 − 1 2^{31}−1 231−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整除，求中必然有一个大于 n \sqrt{n} n 一个小于 n \sqrt{n} n
，很好反证，如果两个数都大于 n \sqrt{n} n，那么这俩数相乘的结果将会大于n
所以没必要枚举2到n - 1所有数，只需要枚举到 n \sqrt{n} 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 a_i ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个正整数 a i a_i ai。
输出格式
对于每个正整数 a i a_i ai，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。
每个正整数的质因数全部输出完毕后，输出一个空行。
数据范围
1≤n≤100,
2≤ai≤2× 1 0 9 10^9 109
输入样例：
2
6
8
输出样例：
2 1
3 12 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开始枚举，直到根号nfor(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 之间素数的具体过程：
-
初始化：列出 2 - 20 的所有整数：2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20 。
-
筛选过程
- 第一步：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 中它们的倍数都已在前面步骤被处理过，没有新的数可划去。
-
结果：经过上述操作，2 - 20 之间剩下的数 2、3、5、7、11、13、17、19 就是该范围内的素数。 这种方法叫埃拉托斯特尼筛法，通过不断划去素数的倍数，能高效找出一定范围内的素数。
【例题】
给定一个正整数 n，请你求出 1∼n 中质数的个数。
输入格式
共一行，包含整数 n。
输出格式
共一行，包含一个整数，表示 1∼n 中质数的个数。
数据范围
1≤n≤ 1 0 6 10^6 106
输入样例：
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;}
}
