因子个数 和因子和

 

【因子个数】

 

实现代码：

int count(int n)///求因子的个数
{
    int s=1;///记录总共的素因子的个数
    for(int i=2;i*i<=n;i++)
        if(n%i==0)
    {
        int a=0;///记录的是每个素因子的个数
        while(n%i==0)
        {
            n/=i;
            a++;
        }
        s=s*(a+1);
    }
    if(n>1)
        s=s*2;
    return s;
}

【因子和】

单独判断：

因子和：一个数的所以因子的和就叫因子和。

证明：牛顿二项式

例如：

12 = 2 * 2 * 3

12的因子为1 2 3 4 6 12  相加和为28

计算方法是把12分解为质因数的表达形式2^2*3

因子和sum = (1 + 2 + 2*2 )*(1 + 3) = 28;

再如
30 = 2 * 3 * 5;
30的因子为1 2 3 5 6 10 15 30相加和为 = 72
因子和sum = (1 + 2)*(1 + 3)*(1 + 5) = 3 * 4 * 6 = 72;

int sum(int n)///求因子的和
{
    int s=1;
    for(int i=2;i*i<=n;i++)
        if(n%i==0)
    {
        int a=1;///记录素因子的乘积
        while(n%i==0)
        {
             n/=i;
             a*=i;
        }
        s=s*(a*i-1)/(i-1);
    }
    if(n>1)
        s=s*(1+n);
    return s;
}

 

打表法：

const int N=500001;  
int p[N];  //p[i]表是i的因子和
void init()    
{     
	int n=N;
	memset(p,0,sizeof(p));
     for(int i=1;i<=n;i++)      //因子和打表
     	for(int j=2;j*i<=n;j++)
     		p[i*j]+=i;
	 
}  

例题：HDU 1215  七夕节