数学
质数
试除法判定质数
给定 n 个正整数 ai，判定每个数是否是质数。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个正整数 ai。
输出格式
共 n 行，其中第 i 行输出第 i 个正整数 ai 是否为质数，是则输出 Yes，否则输出 No。
数据范围
1≤n≤100,
1≤ai≤231−1
输入样例：
输出样例：
#include <bits/stdc++.h>
using namespace std;
bool is_prime(int a) {
if (a < 2) return false;
for (int i = 2; i <= a / i; i++) {
if (a % i == 0) return false;
}
return true;
}
int main() {
int n, a;
cin >> n;
while (n--) {
cin >> a;
if (is_prime(a)) puts("Yes");
else puts("No");
}
return 0;
}
分解质因数
给定 n 个正整数 ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个正整数 ai。
输出格式
对于每个正整数 ai，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。
每个正整数的质因数全部输出完毕后，输出一个空行。
数据范围
1≤n≤100,
2≤ai≤2×109
输入样例：
输出样例：
#include <bits/stdc++.h>
using namespace std;
void divide(int x) {
for (int i = 2; i <= x / i; i++) {
if (x % i == 0) {
int s = 0;
while (x % i == 0) {
x /= i;
s++;
}
cout << i << ' ' << s << endl;
}
}
if (x > 1) cout << x << ' ' << 1 << endl;
cout << endl;
}
int main() {
int n, x;
cin >> n;
while (n--) {
cin >> x;
// cout << x << endl;
divide(x);
}
return 0;
}
筛质数
给定一个正整数 n，请你求出 1∼n 中质数的个数。
输入格式
共一行，包含整数 n。
输出格式
共一行，包含一个整数，表示 1∼n 中质数的个数。
数据范围
1≤n≤106
输入样例：
输出样例：
code
nloglogn
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int primes[N], cnt;
bool st[N];
void get_primes(int n) {
for (int i = 2; i <= n; i++) {
if (st[i]) continue;
primes[cnt++] = i;
for (int j = i + i; j <= n; j += i) {
st[j] = true;
}
}
cout << cnt;
}
int main() {
int n;
cin >> n;
get_primes(n);
return 0;
}
o(n)
pj 是x的最小质因子 ，所以判断到根号n即可
pj <= i的最小质因子
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int primes[N], cnt;
bool st[N];
void get_primes(int n) {
for (int i = 2; i <= n; i++) {
if (!st[i]) primes[cnt++] = i;
for (int j = 0; primes[j] <= n / i; j++) {
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
int main() {
int n;
cin >> n;
get_primes(n);
cout << cnt;
return 0;
}
质数： 大于 1 的整数中 ，如果只包含1和本身这俩个约数
质数的判定1.试除法
分解质因数 试除法
任何数都可以表示成质数的乘积。
N只会被 最小质因子
i%pj == 0
pj 是 I的最小质因子 也是pj * i的最小质因子
i%pj != 0
pj 是 pj * i的最小质因子
对于一个合数x,一定存在最小质因子
假设pj 是x的最小质因子， 当i 美剧导 x/pj
每个数都有一个最小质因子
i是 合数 最小质因子就会停下来
i是质数 pj == i 也会停下来
n + n/2 + n/3 + ... 1
1的倍数 2的倍数 3的倍数
1的约数 2的约束
nlogn
1是所有倍数的约数
int 范围内某个数1500个约数字
222
欧拉函数
1-n 中和n互质的个数
容质原理：
等价
n更好i
34