题目描述

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

样例

2
6
8

2 1
3 1

2 3

算法

(试除法)

1. 这道题也是试除法。
2. 因为要输出每个 质因数的个数，所以从2开始枚举到$\sqrt n$，有约数的话，就一直除它，比如8，会有3个2，那么这样最后8会变成1，不再满足for()循环条件，跳出输出即可。
3. 比如6，先输出2，接下来是3，但是3是比根号6大的，一个数只能有一个比其根号大的素数(不然平方一下就比它本身大了)，所以如果出现了这种情况，那么n本身一定没有除尽，也就一定会大于1，那么继续输出n就可以。

时间复杂度

$O(logn)$~$O(\sqrt n)$

C++ 代码

#include <iostream>

using namespace std;

void divide(int n)
{
    for(int i = 2; i <= n / i; i ++)
        if(n % i == 0)
        {
            int cnt = 0;
            while(n % i == 0) n /= i, cnt ++;
            cout << i << ' ' << cnt << endl;
        }
    if(n > 1) cout << n << ' ' << 1 << endl;
    cout << endl;
}

int main()
{
    int n;
    cin >> n;
    while(n --)
    {
        int x;
        cin >> x;
        divide(x);
    }

    return 0;
}