题目描述
给定 n 个正整数 ai,将每个数分解质因数,并按照质因数从小到大的顺序输出每个质因数的底数和指数。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一个正整数 ai。
输出格式
对于每个正整数 ai,按照从小到大的顺序输出其分解质因数后,每个质因数的底数和指数,每个底数和指数占一行。
每个正整数的质因数全部输出完毕后,输出一个空行。
样例
数据范围
1≤n≤100,
2≤ai≤2×109
输入样例:
2
6
8
输出样例:
2 1
3 1
2 3
算法1
试除法求解质因数,还是只需要求解较小的质因数即可,因为n最多只能包含一个大于sqrt(n)的质因数,所以我们仍然只需要从2枚举到n/i即可,后续只需要判断n是否大于1即可,大于1,即说明该数是n的大于sqrt(n)的质因数,加上即可
for(int i=2;i<=n/i;i++)
if(n%i==0)
while(n%i==0)
这里解释一下为什么不会有合数存在,因为后续存在n%i所以即使n最开始是合数,也会慢慢被i给取余取掉,所以这里取到的数必是质数
时间复杂度
最坏O(sqrt(n))
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,a[N];
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<<endl;
}
if(n>1) cout<<n<<" "<<"1"<<endl;
cout<<endl;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++)
divide(a[i]);
return 0;
}