分解质因数模板

暴力做法 —— 试除法

思想：

我遇到一个质因数，就把它能整除掉的所有后面的数都给整除掉。可能容易不理解的地方在于：我们会不会找到合数没有被小于它的质因数整除掉？
答：不会的。因为我们是从小到大进行枚举因数i，遇到可以整除的就把该因数i的所有因数都除掉了，后面不会找出一个合数了。即当我枚举到i时就意味着我已经把从0~i-1的因子都除干净了，那么当n%i 0， 且0~i-1中没有一个是i的因子，那么i就是一个质数，i就为n的质因子

时间复杂度

O(logn)

板子

void divide(int x)
{
    for(int i = 2; i<=n; i++)
        if(n%i == 0)
        {
            int s = 0;
            while(n%i == 0)
            {
                n /= i;
                s++;
            }
            printf("质因数:%d 个数:%d\n", i, s);
        }
}

进阶版

思想

从暴力法出发，我们发现n当中最多只有一个大于\sqrt{n}的质因子，因此我们只用枚举到\sqrt{n}即可。大于\sqrt{n}的我们单独判断一下。

时间复杂度

O\sqrt{n}

板子

void divide(int x)
{
    // 先枚举小于等于根号n的部分
    for(int i = 2; i<=n/i; i++)
        if(n%i == 0)
        {
            int s = 0;
            while(n%i == 0)
            {
                n /= i;
                s++;
            }
            printf("质因数:%d 个数:%d\n", i, s);
        }
    // 如果上面处理后，n仍大于1， 那么此时n就是那个大于根号n的质因子
    if(n > 1) printf("大于根号n的质因数:%d 个数:1\n",n);
}