Finding Summations of Divisor

Number of primefactorize(n) = p1^x1*p2^x2*p3^x3....pn^xn

summation of divisor(n)=1+r+r^2+r^3......+r^n=(r^n+1-1)/r-1



#include <bits/stdc++.h>
using namespace std;
int divsum(int n)
{
  bool mark[n+1];
  memset(mark, true, sizeof(mark));

  for(int i=2; i*i<=n; i++)
  {
  if(mark[i]==true)
  {
  for(int j=i*2; j<=n; j+=i)
  {
  mark[j]=false;
  }
  }
  }
  int total=1, ret=0;
  for(int i=2; i<=(n); i++)
  {
  if(mark[i]==true)
  {
  int cnt=0;
  if(n%i==0)
  {
  while(n%i==0)
  {
  n/=i;
  cnt++;
  }
ret = (pow(i, cnt+1)-1)/(i-1);
  }
  total = total*ret;
  }
  }
  return total;
}
int main ()
{
int n;
cin >> n;
cout << divsum(n)<<endl;
return 0;
}

Comments

Popular posts from this blog

কন্টেস্ট রিলেটড কিছু বিষয়

Efficiently getting all divisors of a given number

Print sum of prime divisor