试除法判定质数
无论在何种情况下，时间复杂度都是O(sqrt(n))acwing.866.试除法判断质数
试除法判断质数
给定n个正整数ai，判定每个数是否是质数。
输入格式
第一行包含整数n。
接下来n行，每行包含一个正整数ai。
输出格式
共n行，其中第 i 行输出第 i 个正整数ai是否为质数，是则输出“Yes”，否则输出“No”。
数据范围
1 ≤ n ≤ 100,
1 ≤ ai ≤ 231−1
输入样例：
226
输出样例：
YesNo
AC代码：
#include <bits/stdc++.h>using namespace std;bool isprime(int n){if(n<2)return false;for(int i=2;i<=n/i;i++){if(n%i==0)return false;}return true;}int main(){ios::sync_with_stdio(false);cin.tie(0);int n;cin>>n;while(n--){int a;cin>>a;if(isprime(a))cout<<"Yes"<<'\n';else cout<<"No"<<'\n';}return 0;}
注意点：
一开始要判定n小于2的情况for(int i=2;i<=n/i;i++)中的i<=n/i，不能写成i*i<=n，极端情况下会爆；也不建议写成i<=sqrt(n)，因为sqrt很慢
试除法分解质因数
n中最多只包含一个大于sqrt(n)的质因子，这个唯一的落网之鱼就是其本身就是质数，比如37。最坏情况下，时间复杂度为O(sqrt(n))，但一般在O(logn)到O(sqrt(n))之间。直接枚举1到n就可以，因为当我们枚举到i的时候，就意味着我们已经把从2到i-1之间的质因子除干净了，因此i一定是质数。AcWing867. 分解质因数
给定n个正整数ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。
输入格式
第一行包含整数n。
接下来n行，每行包含一个正整数ai。
输出格式
对于每个正整数ai,按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。
每个正整数的质因数全部输出完毕后，输出一个空行。
数据范围
1≤n≤100,
1≤ai≤2∗109
输入样例：
268
输出样例：
2 13 12 3
AC代码：
#include <bits/stdc++.h>using namespace std;void divide(int n){for(int i=2;i<=n/i;i++){if(n%i==0){int s=0;while(n%i==0)n/=i,s++;cout<<i<<' '<<s<<'\n';}}if(n>1)cout<<n<<' '<<1<<'\n';cout<<'\n';}int main(){ios::sync_with_stdio(false);cin.tie(0);int n,a;cin>>n;while(n--){cin>>a;divide(a);}return 0;}
注意点：
以上。
