2. 分解质因数
分析：假设枚举到 i, n 中一定不包含 2 ~ i - 1 之间的质因子, 又因为n % i == 0,即 n 为 i 的倍数, 所
以 i 当中也不包含 2 ~ i - 1 之间的质因子, 所以 i 一定是质数.
1.朴素做法 ---- O(n)O(n)
void divide(int n){
    for(int i = 2; i <= n;  i ++){
        if(n % i == 0){
            int s = 0;
            while(n % i == 0){
                n /= i;
                s ++;
            }

            cout << i << ' ' << s << endl;
        }
    }
}
2.改进版 ---- O(n√)O(n)(不一定)

void divide(int n){
    for(int i = 2; i <= n / i; i ++){//n中最多包含一个大于sqrt(n)的质因子
        if(n % i ==0){
            int s = 0;
            while(n % i == 0){
                n /= i;
                s ++;
            }
            cout << i << ' ' << s << endl;
        }
    }
    if(n > 1) cout << n << ' ' << '1' << endl;//大于sqrt(n)的质因子
}
注意：当 n = 2k2k时, 时间复杂度为logn, 因此其时间复杂度介于 logn ~ n√n之间

典型例题
分解质因数