代码

#include <iostream>

using namespace std;

int n;

void divide(int n)
{
    // Brute-Force暴力

    // for (int i = 2; i <= n; i++) {
    //     // 当n % i == 0 的时候， n当中已经不包含从2 ~ i-1之间的所有质因子了
    //     // n 是 i 的倍数，所以 i 当中也不包含 2 ~ i-1 之间的所有质因子，因此i一定是一个质数
    //     // 所有的合数必可以被质因子分解
    //     // 从2开始除的，因此必不可能有合数
    //     if (n % i == 0) {
    //         int s = 0;
    //         while (n % i == 0) {
    //             n /= i;
    //             s++;
    //         }
    //         cout << i << " " << s << endl;
    //     }
    // }

    // **************************************************************************
    // n中最多只包含一个 > sqrt(n) 的质因子
    //      证明：
    //          假设 n中包含两个 > sqrt(n) 的质因子， 这两个数相乘一定会 > n, 因此矛盾
    //          得证 n中最多只包含一个  > sqrt(n) 的质因子
    // **************************************************************************

    // 根据上面的结论， 我们可以先枚举出所有 <= sqrt(n)的质因子， 然后最后剩下的那个， 就是 >sqrt(n)的质因子
    // 时间复杂度从 O(N) 降低到了 O(sqrt(N))

    for (int i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            int s = 0;
            while (n % i == 0) {
                n /= i;
                s++;
            }
            cout << i << " " << s << endl;
        }
    }
    if (n > 1) {  // 如果 n>1 说明最后剩下的数一定是 >sqrt(n)的那个质因子
        cout << n << " " << 1 << endl;
    }
}

int main()
{
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        divide(x);
        puts("");
    }
    return 0;
}