How can i find the sum of divisors of a given number in a faster way?

[shivpratap]

I m solving a problem to find the sum of divisors of a given number(the number is a large one),...i hv written the code bt it's exceding the time limit...hw can i reduce the time in such cases...pls help me....i m a beginner 2 programming in c :)
Hre is my code:

#include<stdio. h>
int main()
{
long long int k,n,t,sum=0;
scanf("%lld",&t );
while(t)
{
scanf("%lld",&n );
for(k=1;k<n;k++ )
{
if(n%k==0)
{
sum=sum+k;
}
}
printf("%lld\n" ,sum);
t--;
sum=0;
}
system("pause") ;
return 0;
}

[YarrOfDoom]

There's a lot of numbers you can easily skip here, you just have to think about the maths behind it.
Think about this for instance: "What's the highest divisor I'm ever going to find for a number (excluding the number itself of course)?"
If you can calculate this number (or an approximation of it) before the loop, you only have to go up to this number, instead of all the way up to the given number.
I'm sure if you look into it a little bit further you can find other ways to speed it up as well.

PS: If you post your code in code-tags (put [code] in front of your code and [/code] behind it), it is much easier to read for everyone. More posting guidelines can be found here.

[donbock]

Remember that divisors come in pairs. Every time you find a divisor with your loop you can then find its partner. Then your loop only needs to find half the divisors.

[shivpratap]

@yaarofdoom

Thanks,this was my 1st post i dis forum,ill tk care abt it next time...btw i know i can cutshort this loop if replace n with n/2 in the loop......bt still it's consuming more time.....ny better algorithm i can use???.....pls help

@donbock

Thanks can u suggest a better algorithm for this 1??

[shivpratap]

@yaarofdoom

Thanks,this was my 1st post i dis forum,ill tk care abt it next time...btw i know i can cutshort this loop if replace n with n/2 in the loop......bt still it's consuming more time.....ny better algorithm i can use???.....pls help

@donbock

Thanks can u suggest a better algorithm for this 1??

[newb16]

...i dis forum,ill tk care abt it

There are 3 words I understand (forum, care, it) and 5 that I either don't know or that look misplaced in this context ( 'i' and 'ill'). Maybe it's not that important, though.
I'd find all prime factos of the number in question ( with their respective powers) and then compute all possible divisors from them. ( if n = p_1^k_1 * ... * p_n^k_n , you have (k_1+1)*...*(k_ n+1) possible divisors.

[shivpratap]

@yaarofdoom

Thanks,this was my 1st post i dis forum,ill tk care abt it next time...btw i know i can cutshort this loop if replace n with n/2 in the loop......bt still it's consuming more time.....ny better algorithm i can use???.....pls help

@donbock

Thanks can u suggest a better algorithm for this 1??

[shivpratap]

@yaarofdoom

Thanks,this was my 1st post i dis forum,ill tk care abt it next time...btw i know i can cutshort this loop if replace n with n/2 in the loop......bt still it's consuming more time.....ny better algorithm i can use???.....pls help

@donbock

Thanks can u suggest a better algorithm for this 1??

[YarrOfDoom]

Could you please stop copy-pasting the same post over and over again?
How about you show some of the efforts you have done yourself to implement the suggestions we have given you, so we can help you on that?
And putting some more effort into your spelling would be greatly appreciated as well (maybe you should read the posting guidelines again).

[donbock]

As you said, you could limit your search for divisors to the range from 1 to n/2. However, you can do even better. Consider your divisor search ... you start with 1 and find its partner (n), then find the next divisor (i) and its partner (n/i). Notice that the partners are larger than the initial divisors: n > 1, n/i > i, etc. As your divisors increase the partners decrease. You continue looking for divisors until the partner is less than or equal to the divisor. After that, all you're doing is finding another instance of a pair you already found.

So ... the trick for deciding when to look for divisors is when the partner is less than or equal to the divisor. Think about the arithmetic for awhile -- how can you characterize this transition point?