文章目录
一、质数
二、质数的判定——试除法
题目描述
给定 n 个正整数 a i 判定每个数是否是质数。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个正整数 a i
输出格式
共 n 行，其中第 i 行输出第 i 个正整数 a i
是否为质数，是则输出 Yes，否则输出 No。
数据范围
具体实现
1. 实现思路
2. 实现代码
#include <bits/stdc++.h> using namespace std; bool is_prime(int x) { //判断这个数是否大于等于 2 if (x < 2) { return false; } //判断是否还有别的约束 for (int i = 2; i <= x / i; i ++ ) { if (x % i == 0) { return false; } } return true; } int main() { int n; cin >> n; while (n -- ) { int x; cin >> x; if (is_prime(x)) { puts("Yes"); } else { puts("No"); } } return 0; }
三、分解质因数——试除法
题目描述
输入样例
2
6
8
输出样例
2 1
3 1
（空行）
2 3
（空行）
具体实现
1. 实现思路
我们需要注意的是，质因数的底数必须是质数。
暴力写法：从小到大枚举 n nn 的所有质因数，如果 n nn 模 i ii 等于 0 00，就求出 i ii 的次数即可。
void divide(int x) { for (int i = 2; i <= x; i ++ ) { if (x % i == 0) //i一定是质数 { int s = 0; while (x % i == 0) { x /= i; s ++ ; } cout << i << ' ' << s << endl; } } }
2. 实现代码
#include <bits/stdc++.h> using namespace std; void divide(int x) { for (int i = 2; i <= x / i; i ++ ) { if (x % i == 0) //i一定是质数 { 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; cin >> n; while (n -- ) { int x; cin >> x; divide(x); } return 0; }
四、筛质数
题目描述
给定一个正整数 n，请你求出 1 ∼ n 中质数的个数。
输入格式
共一行，包含整数 n 。
输出格式
共一行，包含一个整数，表示 1 ∼ n 中质数的个数。
数据范围
1. 朴素筛法
1.1 实现思路
- 首先，我们将所有的数放入一个数组当中，然后从前往后观察，依次将每一个数的倍数删除掉。
- 经过这样筛选过后，剩下的数就都是质数。
1.2 实现代码
#include <bits/stdc++.h> using namespace std; const int N= 1000010; //cnt表示质数的个数 int primes[N], cnt; bool st[N]; void get_primes(int n) { for (int i = 2; i <= n; i ++ ) { if (st[i]) { //跳出本次循环 continue; } //primes[]数组存储质数 primes[cnt ++ ] = i; //去除倍数 for (int j = i + i; j <= n; j += i) { st[j] = true; } } } int main() { int n; cin >> n; get_primes(n); cout << cnt << endl; return 0; }
2. 线性筛法
2.1 实现思路
2.2 实现代码
#include <bits/stdc++.h> using namespace std; const int N= 1000010; 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) //primes[j]一定是i的最小质因子 { break; } } } } int main() { int n; cin >> n; get_primes(n); cout << cnt << endl; return 0; }
