Sunday, June 30, 2013

Sum of Divisors of a Number

Sum of divisors of a Number can be found by the following formula.

Now the code. Following function calculate sum of divisors of a number-

#define i64 long long

i64 power(i64 N,i64 P)
{
	i64 sum=1,i;
	
	if(P==0)return 1;
	else
	{
		for(i=1;i<=P;i++)
			sum=sum*N;
		return sum;
	}
}

i64 sumofdivisor(i64 n)
{
	i64 sum=1,i,count;
	i64 sq=(i64)sqrt(n);
	
	for(i=0;prime[i]<=sq;i++)
	{
		count=0;
		while(n%prime[i]==0)
		{
			count++;
			n/=prime[i];
		}
		sum*=(i64)(power(prime[i],count+1)-1)/(prime[i]-1);
	}
	if(n>1)
		sum*=(n+1);
	return sum;
}

No comments:

Post a Comment