$算术基本定理：任何一个大于1的自然数N,如果N不为质数$

$那么N可以唯一分解成有限个质数的乘积N={p_1}^{a_1} * {p_2}^{a_2}…*{p_n}^{a_n} $

$且最多只有一个大于\sqrt{n}的质因子，这里P1<P2<P3......<Pn均为质数，其中指数ai是正整数。$

$时间复杂度：\sqrt{n}$

#include<bits/stdc++.h>
using namespace std;

void divide(int n){
    for(int i=2;i<=n/i;i++){
        if(n%i==0){       //n不包含任何从2到i-1之间的质因子（已经被除干净了）
                          //(n%i==0)所以i也不包含何从2到i-1之间的质因子，由质数的定义可知，保证了i是质数
            int s=0;
            while(n%i==0) n/=i,s++;  
            cout<<i<<' '<<s<<endl;
        }
    }  
    if(n>1) cout<<n<<' '<<1<<endl;    //最多只有一个大于根下n的质因子（两个相乘就大于n了）
    cout<<endl;
}

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        divide(a);
    }
}