473,948 Members | 17,317 Online

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

6 New Member
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;
}
Mar 19 '10 #1
15 20645
YarrOfDoom
1,247 Recognized Expert Top Contributor
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.
Mar 19 '10 #2
donbock
2,426 Recognized Expert Top Contributor
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.
Mar 20 '10 #3
shivpratap
6 New Member
@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??
Mar 20 '10 #4
shivpratap
6 New Member
@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??
Mar 20 '10 #5
newb16
687 Contributor
...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.
Mar 20 '10 #6
shivpratap
6 New Member
@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??
Mar 20 '10 #7
shivpratap
6 New Member
@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??
Mar 20 '10 #8
YarrOfDoom
1,247 Recognized Expert Top Contributor
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).
Mar 20 '10 #9
donbock
2,426 Recognized Expert Top Contributor
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?
Mar 21 '10 #10