试除法分解质因数 O(logn)~O(sqrt(n))

枚举的 i 一定是质数（因为只要枚举到了 i 就说明 2到i-1 中 没有i 的质因子）
最多有一个大于sqrt(n)的质因子 ，因为如果有两个，他们的乘积就大于n了。

C++ 代码

#include<iostream>

using namespace std;
const int N=105;

int n;
int a[N];

void divide(int n)
{
    for(int i=2;i<=n/i;i++){
        if(n%i==0){// i一定是质数
            int s=0;
            while(n%i==0){
                n/=i;
                s++;
            }
            printf("%d %d\n",i,s);
        }
    }
    //n最多有一个大于sqrt(n)的质因子
    if(n>1)printf("%d 1\n",n);
    puts("");
    return ;
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        divide(a[i]);
    }

    return 0;
}