AcWing 867. 分解质因数

AcWing 867. 分解质因数

AcWing 867. 分解质因数

算数基本定理：任何一个大于1的整数n都可以分解成若干个质因数的连乘积，如果不计各个质因数的顺序，那么这种分解是唯一的。即： x = a 1 p 1 × a 2 p 2 × a 3 p 3 × a 4 p 4 × . . . × a n p n x = a_1^{p_1}times a_2 ^{p_2}times a_3 ^{p_3}times a_4 ^{p_4}times ...times a_n^{p_n} x=a1p1​​×a2p2​​×a3p3​​×a4p4​​×...×anpn​​，其中 n > 1 n>1 n>1， p 1 ≤ p 2 ≤ . . . ≤ p n p_1le p_2 le ...le p_n p1​≤p2​≤...≤pn​且都是 x x x 的质因子简易证明可以这样想，若一个数是合数，它就一定存在因子，若它的因子还是合数，那么可以继续向下分，直到无法继续分为止；若一个数是质数，那么它的因子就是1和本身。怎么分解质因子呢？可以从小到大枚举 x x x 的小因子，然后枚举到质因子时，将该质因子除干净。最后若 x > 0 x > 0 x>0 那么表示 x x x 还存在一个大质因子，就是当前的 x x x 。 代码：

时间复杂度： O ( n n ) O(nsqrt n) O(nn ​)

#include 
#include 
#include 

using namespace std;

int n;

void divid(int x)
{
    for (int i = 2; i <= x / i; i ++ )
    {
        if (x % i == 0)
        {
            int s = 0;
            while (x % i == 0) x /= i, s ++ ; //将质因子除干净
            cout << i << " " << s << endl;
        }
    }
    if (x > 1) cout << x << " " << 1 << endl; //存在一个大的质因子
    puts("");
}

int main()
{
    cin >> n;
    
    while (n -- )
    {
        int x;
        cin >> x;
        divid(x);
    }
    
    return 0;
}

参考资料：
https://www.acwing.com/activity/content/code/content/49974/