题目描述

给定 n 个正整数 ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。

输入格式
第一行包含整数 n。

接下来 n 行，每行包含一个正整数 ai。

输出格式
对于每个正整数 ai，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。

每个正整数的质因数全部输出完毕后，输出一个空行。

数据范围
1≤n≤100,
1≤ai≤2×109

样例

输入样例：
2
6
8
输出样例：
2 1
3 1

2 3

算法1

(暴力枚举) $O(logn~根号n之间)$

时间复杂度

在每次循环之前 判断n==1 如果n==1 直接break。
当n是2的倍数或…的倍数时
如是16 时 在i==2时会进入while循环 出循环时 n=1,这时可直接跳出循环，不必再进行。可使在Logn

参考文献

分解质因数

分解的是质因数，但在for循环中有合数怎么办？
不影响，因为在进入该合数之前，如果该合数是n的因子，那么该合数的质因子一定被循环过
如12=2×6 但不会进行到6 因为6=2×3，在进入6前，6的质因子已经被循环过，6已经被分解了。
n最多只包含一个大于根号n的质因子
如果有两个，则这两个相乘一定大于n 不成立。
所以for循环不必进行到n 只用进行到根号n即可。
如果结束循环n>1，证明n存在一个大于根号n的质因子，直接输出即可，而且指数一定是1

C++ 代码

#include<iostream>
using namespace std;
void divid(int n){
    for(int i=2;i<=n/i;i++){
        if(n==1)
        break;
        int cnt=0;
        if(n%i==0){
            while(n%i==0){
                cnt++;
                n/=i;
            }
            cout<<i<<" "<<cnt<<endl;
        }
    }
    if(n>1) cout<<n<<" "<<1<<endl;
    cout<<endl;
}
int main(){
    int n,t;
    cin>>t;
    while(t--){
    cin>>n;
    divid(n);}
    return 0;
}