Find the sum of factors.

I tried to solve SPOJ : Sum of Factors. But get TLE. Please tell me how to solve this…

@rashedcs If N=$p_1^a$x$ p_2^b$x…x$p_n^m$ where p_1, p_2,.., p_n are the prime factors of N, then sum of all factors of a number including the number itself is equal to the following expression:

Sum=((p_1^{a+1}-1)/(p_1-1))x((p_2^{b+1}-1)/(p_2-1))x…x((p_n^{m+1}-1)/(p_n-1))

And for calculating the prime factors of a number you can store prime numbers upto 100005(that will be sufficient for this question) in an array using Sieve.

1 Like

You can do it in sqrt(n) time.

int i = 1,ans = 0;
while (i*i <= n){
    if (n%i == 0){
        ans += i;
        if (i*i != n) ans += n/i;
    }
    i ++;
}
1 Like

int n,i,s
s=0;
cin>>n;
for(i=1;i<=n;i++)
{
if(i%n==0)
{s=s+i;
}
}
cout<<“sum of factors of”<<n<<“is”<<s;

This can be done without calculating primes too…my excepted code G0mXjQ - Online C++ Compiler & Debugging Tool - Ideone.com

@srd091 you are correct.

1 Like

I tried using sieve …but get WA.
Code link : gbOV8R - Online C++0x Compiler & Debugging Tool - Ideone.com

@rashedcs you are taking result as int and final answer can be greater than 10^9, take result as long long int.

1 Like

If long long int then get WA…

@rashedcs the return type of function is still int, you need to change it to long long int. Your accepted solutions with above corrections: A3JBAP - Online C++ Compiler & Debugging Tool - Ideone.com

tnq so much @srd091.

1 Like

@mathecodician This method is infeasible or gives TLE for this problem!

@rashedcs If you feel your question has been answered mark it as accepted.