试除法分解质因数

•  证明一下循环里面的 i 一定是一个质数：假如 i 是一个合数，那么它一定可以分解成多个质因子相乘的形式，这多个质因子同时也是 a 的质因子且比 i 要小，而比 i 小的数在之前的循环过程中一定是被条件除完了的，所以 i 不可能是合数，只可能是质数
• n中最多只含有一个大于sqrt(n)的质因子。证明通过反证法：如果有两个大于sqrt(n)的质因子，那么相乘会大于n，矛盾。证毕

贴上代码：

#include 
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 cnt = 0;
                while(a % i == 0)
                {
                    a /= i;
                    cnt++;
                }
                
                cout << i << ' ' << cnt << endl;
            }
        }
        if(a > 1) cout << a << ' ' << 1 << endl;
        cout << endl;
    }
    return 0;
}