分解质因数

题目描述

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

输入格式
第一行包含整数 n。
接下来 n行，每行包含一个正整数 ai。

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

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

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

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

2 3

本人在写这道题时的俩个疑问

1.为什么for循环是从 i = 2 到 i <= n / i

答: 首先质数一定得是大于1的,所以i从2开始.

把x分解成质因子时,最多只包含一个大于sqrt(n)的质因子
所以我们可以先遍历小于等于sqrt(n)的质数
i <= sqrt(n)  //每次遍历时会调用sqrt函数,速度较慢
所以 i * i <= n  //i 与 i相乘容易爆int
所以 i <= n / i  //这种写法最完美

2.明明是求质因子,为什么不用担心在for循环时遍历到合数

答: for循环后接if判断语句,如果 n % i ==0
那么说明 n 是 i 的倍数
此时 n 中已不含从 2 到 i - 1 的质因子
所以 i 中也肯定不含
如果 i 是合数,那么 i 一定可以由2 ~ i - 1中的质因子组成
与前面推到出来的结果相悖了
所以 i 一定是一个质数
(此处代码隐含了对合数的筛除)

c++代码

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a;
        cin>>a;
        for(int i = 2; i <= a / i; i++)
        {
            if(a % i == 0)
            {
                int s =0;
                while(a % i == 0)
                {
                    a /= i;
                    s++;
                }
                cout<<i<<" "<<s<<endl;
            }
        }
        if(a > 1) cout<<a<<" "<<1<<endl;
        cout<<endl;
    }
}

小白的个人理解,如有不对请大佬指正