一、试除法判定质数
算法模板：
bool is_prime(int x) { if (x < 2) return false; for (int i = 2; i <= x / i; i ++ ) if (x % i == 0) return false; return true; }
例题：
给定 n 个正整数 ai，判定每个数是否是质数。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个正整数 a。
输出格式
共 n 行，其中第 i 行输出第 i 个正整数 a 是否为质数，是则输出 Yes，否则输出 No。
数据范围
1≤n≤100
1≤ai≤2^31−1
输入样例：
2 2 6
输出样例：
Yes No
#include <bits/stdc++.h> using namespace std; bool is_prime(int x) { 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)) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }
二、试除法分解质因数
算法模板：
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; }
例题：
给定 n 个正整数 ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个正整数 ai。
输出格式
对于每个正整数 ai，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。
每个正整数的质因数全部输出完毕后，输出一个空行。
数据范围
1≤n≤100
2≤ai≤2×10^9
输入样例：
2 6 8
输出样例：
2 1 3 1 2 3
#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=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; }
三、试除法求所有约数
算法模板：
vector<int> get_divisors(int x) { vector<int> res; for (int i = 1; i <= x / i; i ++ ) if (x % i == 0) { res.push_back(i); if (i != x / i) res.push_back(x / i); } sort(res.begin(), res.end()); return res; }
例题：
给定 n 个正整数 ai，对于每个整数 ai，请你按照从小到大的顺序输出它的所有约数。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个整数 ai。
输出格式
输出共 n 行，其中第 i 行输出第 i 个整数 ai 的所有约数。
数据范围
1≤n≤100
2≤ai≤2×10^9
输入样例：
2 6 8
输出样例：
1 2 3 6 1 2 4 8
#include <bits/stdc++.h> using namespace std; vector<int> get_divisors(int n) { vector<int> res; for(int i=1;i<=n/i;i++) { if(n%i==0) { res.push_back(i); if(i!=n/i)res.push_back(n/i); } } sort(res.begin(),res.end()); return res; } int main() { int n; cin>>n; while(n--) { int x; cin>>x; auto res=get_divisors(x); for(auto t: res)cout<<t<<" "; cout<<endl; } return 0; }
四、最大公约数
算法模板：
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
例题：
给定 n 对正整数 ai,bi，请你求出每对数的最大公约数。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个整数对 ai,bi
输出格式
输出共 n 行，每行输出一个整数对的最大公约数。
数据范围
1≤n≤10^5
1≤ai,bi≤2×10^9
输入样例：
2 3 6 4 6
输出样例：
3 2
#include<bits/stdc++.h> using namespace std; int gcd(int a,int b) { return b? gcd(b,a%b) : a; } int main() { int n; cin>>n; while(n--) { int a,b; cin>>a>>b; cout<<gcd(a,b)<<endl; } return 0; }
