题目描述

质因数分解
题目已知，n为两个质数的乘积，可知n有且仅有两个因数，由于普通枚举会超时，推理得知，教小因数必然小于根号n
因此从小到大枚举，如果能除尽（没有余数）则输出两者的商，算法时间复杂度达（logN）

样例

输入 21
输出 7

算法1

(暴力枚举) $O(log（N）)$

C++ 代码

#include <iostream>
#include <math.h>

using namespace std;

int main()
{
    int n,p;
    cin >> n;
    int u = sqrt(n);
    for(p = 2 ; p <= u ; p++){
        if(n % p == 0) break;
    }
    cout << n / p << endl;
    return 0;
}