题目描述

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

输入格式

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

输出格式

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

数据范围

• 1 ≤ n ≤ 100
• 2 ≤ ai ≤ 2×10^9

输入样例

2
6
8

输出样例

2 1
3 1

2 3

解题

偶数因子（比如2）

• 当i=2时，如果x能被2整除，while循环会把所有的2都除干净。
• 例如，24=2^3*3，第一次循环i=2，会把24除到只剩3。
• 后续i=3时，发现x%3==0，再处理3。
• 这样不会重复统计2，也不会遗漏2。

其他因子

• 以此类推，3、5、7等也会被依次处理。
• 整个算法实际上就是从小到大依次筛选质因数，每发现一个新的质因数，都把它的所有幂次从x中除掉。

为什么不会“漏掉”偶数因子？

• 只要x里有偶数因子（比如2），它一定会被i=2筛出来，不会漏。
• 只要质因子（无论偶数还是奇数）出现了，都能被统计到。

为什么不会“重复”统计？

• 因为每次while循环都把当前质因数的所有幂次除掉了，后面不会再碰到它。

总结

• 偶数因子不会遗漏，也不会重复统计。
• 这种写法保证了所有质因数及其次数都被完整准确统计。
• “筛选出偶数因子”正是算法的本意之一。

代码

#include<iostream>

using namespace std;

int n;

void divide(int n)
{
    for(int i = 2 ; i <= n / i ; i ++)
    {
        if(n % i == 0)
        {
            int s = 0;
            while(n % i == 0)
            {
                n /= i;
                s ++;
            }
            printf("%d %d\n",i , s);
        }
    }

    if(n > 1) printf("%d %d\n", n, 1);
}

int main()
{
    scanf("%d",&n);

    while(n --)
    {
        int x;
        scanf("%d",&x);
        divide(x);
        puts("");
    }
}