AcWing 867. 分解质因数
原题链接
简单
作者:
渐修
,
2024-04-09 23:38:12
,
所有人可见
,
阅读 1
/*
1:n最多只有一个大于根号n的质因子;
2:i从2枚举到根号n,若n%i等于0,则将此质因子除干净(n不断/i) 另外:此时2到i-1的质因
子已经被n除干净,且n是i的倍数,(n含有的质因子一定包含i的质因子)说明2~i-1中不含i的
质因子,说明i是质数,则i是n的质因子
*/
#include<iostream>
using namespace std;
void dive(int n)
{
for(int i=2;i<=n/i;i++)
{
if(n%i==0)
{
int cnt=0;
while(n%i==0)
{
cnt++;
n/=i;
}
cout<<i<<" "<<cnt<<endl;
}
}
if(n>1)
cout<<n<<" "<<1<<endl;
}
int main()
{
int n;
cin>>n;
while(n--)
{
int x;
cin>>x;
dive(x);
puts("");
}
return 0;
}