质数
质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。定义质数又称素数。
试除法判定质数
分解质因数
质数筛
埃氏筛法
线性筛法
AcWing 866. 试除法判定质数 原题链接
给定n个正整数aiai，判定每个数是否是质数。
输入格式
第一行包含整数n。
接下来n行，每行包含一个正整数aiai。
输出格式
共n行，其中第 i 行输出第 i 个正整数aiai是否为质数，是则输出“Yes”，否则输出“No”。
数据范围
1≤n≤1001≤n≤100, 1≤ai≤231−11≤ai≤231−1
输入样例：
2
2
6
输出样例：
Yes
No
private static boolean check(int x) {
if (x <= 1) return false;
for (int i = 2; i <= x / i; i++) {
if (x % i == 0) {
return false;
}
}
return true;
}
AcWing 867. 分解质因数 原题链接
给定n个正整数aiai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。
输入格式
第一行包含整数n。
接下来n行，每行包含一个正整数aiai。
输出格式
对于每个正整数aiai,按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。
每个正整数的质因数全部输出完毕后，输出一个空行。
数据范围
1≤n≤1001≤n≤100, 1≤ai≤2∗1091≤ai≤2∗109
输入样例：
2
6
8
输出样例：
2 1
3 1
2 3
private static void decompose(int x) {
for (int i = 2; i <= x / i; i++) {
int mul = 0;
if (x % i == 0) {
while (x % i == 0) {
mul++;
x /= i;
}
out.println(i + " " + mul);
}
}
if (x > 1) out.println(x + " " + 1);
}
AcWing 868. 筛质数 原题链接
给定一个正整数n，请你求出1~n中质数的个数。
输入格式
共一行，包含整数n。
输出格式
共一行，包含一个整数，表示1~n中质数的个数。
数据范围
1≤n≤1061≤n≤106
输入样例：
8
输出样例：
4
埃氏素筛
static int[] primes;
static int count;
static boolean[] isVis;
public static void main(String[] args) {
int n = in.nextInt();
primes = new int[n + 1];
isVis = new boolean[n + 1];
for (int i = 2; i <= n; i++) {
if (!isVis[i]) {
primes[count++] = i;
for (int j = i + i; j <= n; j += i) {
isVis[j] = true;
}
}
}
out.println(count);
out.flush();
out.close();
}
线性素筛
static int[] prime;
static int count;
static boolean[] isVis;
private static void primeSieve(int n) {
for (int i = 2; i <= n; i++) {
if (!isVis[i]) {
prime[count++] = i;
}
for (int j = 0; prime[j] <= n / i; j++) {
isVis[i * prime[j]] = true;
if (i % prime[j] == 0) {
break;
}
}
}
}