从小到大枚举所有数,
根据算术基本定理,不考虑排列顺序的情况下,每个正整数都能够以唯一的方式表示成它的质因数的乘积。
这里有个性质:n中最多只含有一个大于sqrt(n)的因子,最后如果n还是>1,说明这就是大于sqrt(n)的唯一质因子,输出即可。
#include<bits/stdc++.h>
using namespace std;
int n;
void prime(int x)
{
for(int i=2;i<=x/i;i++),要写成i<=x/i(优化),不然会超时
{
if(x%i==0)
{
int t=0;
while(x%i==0)
{
x/=i;
t++;
}
printf("%d %d\n",i,t);//因为是从小到大枚举的,所以输出时就是以从小到大的顺序输出的
}
}
if(x>1)printf("%d %d\n",x,1);//最后一个质因子,直接输出即可
puts("");
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
int a;
scanf("%d",&a);
prime(a);
}
return 0;
}