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;
}
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
Post a Comment