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:


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

@srd091 you are correct.

1 Like

I tried using sieve …but get WA.
Code link :

@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:

tnq so much @srd091.

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

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

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

int n,i,s
cout<<“sum of factors of”<<n<<“is”<<s;

This can be done without calculating primes too…my excepted code