(O(根号n))分解质因数

分解质因数模板

暴力做法 —— 试除法

思想:

我遇到一个质因数,就把它能整除掉的所有后面的数都给整除掉。可能容易不理解的地方在于:我们会不会找到合数没有被小于它的质因数整除掉?
答:不会的。因为我们是从小到大进行枚举因数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);
}

发表回复

您的电子邮箱地址不会被公开。