题目描述

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

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

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

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

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

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

样例

输入样例：

2
6
8

输出样例：

2 1
3 1

2 3

C++ 代码 (试除法)

#include <iostream>
#include <algorithm>

using namespace std;

void divide(int x)
{
  /*
        i不用循环到初始x的平方根 只用循环到剩余x的平方根
        如果i超过剩余x的平方根 那么就说明剩余x是一个质数 
        就不需要再循环了
  */
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)  // i 一定是个质数
        {
            int s = 0;
            while (x % i == 0) x /= i, s ++;  // 求次数
            cout << i << ' ' << s << endl;
        }

    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

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

    return 0;
}

几个注意点

1. 有同学会担心输出的因子i可能会是合数，这种担心是多余的。 如果 x % i == 0 的话，则i一定是质数。 当我们枚举到i时就意味着此时的x中已经不包含任何从 2 ~ i - 1 之间的质因子了(被除干净了)，由 x % i == 0 成立，则x是i的倍数，因此i也不包含从 2 ~ i - 1 之间的质因子, 从而i为一个质数

2. 补充一个性质： x中最多只包含一个大于sqrt(x)的质因子 (如果有两个相乘之后会大于x) 此性质可以将原来的朴素写法优化成现在的代码。 即先算出sqrt(x)之前的质因子，再算大于sqrt(x)的质因子， 时间复杂度由O(n) 优化为O(sqrt(n))

3. 正整数的质因数分解可将正整数表示为一连串的质因子相乘，质因子如重复可以用指数表示

如有错误 欢迎指正