求一个数所有因子个数和因子和

柔情只为你懂 2023-07-02 07:28 2阅读 0赞

**一、求一个数所有因子个数**  
若能整除i，则不断除i，并记录i的次数。  
则除到最后存在两种情况  
当x == 1，这说明 x 没有其他因子了，得到答案；  
当x != 1, 这时 x 为其一个素数因子（且这个因子大于 根号x ）,所以结果最后再乘2，得到因子个数。

///求一个数所有因子的个数（包括1和它本身）
    ll countnum(ll x) 
    { 
        ll ans=1;
        for(ll i=2; i*i<=x; i++)
        { 
            if(x%i==0)
            { 
                ll temp=0;
                while(x%i==0)
                { 
                    x/=i;
                    temp++;
                }
                ans*=(temp+1);
            }
        }
        if(x>1)
            ans*= 2;
        return ans;
    }

素因子分解求因子个数

const int N = 100000 + 5;
    bool prime[N];//prime[i]表示i是不是质数
    int p[N], tot;//p[N]用来存质数
    void init()
    { 
        for(int i = 2; i < N; i ++)
            prime[i] = true;//初始化为质数
        for(int i = 2; i < N; i++)
        { 
            if(prime[i])
                p[tot ++] = i;//把质数存起来
            for(int j = 0; j < tot && i * p[j] < N; j++)
            { 
                prime[i * p[j]] = false;
                if(i % p[j] == 0)
                    break;//保证每个合数被它最小的质因数筛去
            }
        }
    }
    
    ll sum(ll tmp)
    { 
        ll ans=1;
        for(int i=0;i<tot&&tmp>1;i++)
        { 
            ll cnt=1;
            if(tmp%p[i]==0)
            { 
                while(tmp%p[i]==0)
                { 
                    tmp/=p[i];
                    cnt++;
                }
                ans*=cnt;
            }
        }
        return ans;
    }

**一、求一个数所有因子和**  
思路类似：

///所有因子的和（包括1和它本身）
    ll calcsum(ll x) 
    { 
        ll ans = 1;
        for(ll i=2; i*i<=x; i++)
        { 
            if(x%i==0)
            { 
                ll temp=1;
                while(x%i==0)
                { 
                    x/=i;
                    temp*=i;
                }
                ans*=(temp*i-1)/(i-1);
            }
        }
        if(x>1)
            ans *= (1 + x);
        return ans;
    }