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?

[shivpratap]

I have improved my code a lot now but is it possible to reduce its time further without making a major change in this algorithm??....pls suggest...

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

[newb16]

Well, you can move

if(n/i==i)
     sum=sum-i;

somewhere outside the loop so that it doesn't check it at each iteration.
But without change in algorithm, if given a number that is a product of powers of several small prime numbers, it will check every possible divisor upto sqrt(n).

[donbock]

I have a couple of questions regarding the requirements ...

I notice that for a given number n, you don't include divisors 1 and n in the sum. Is that what you want?

I also notice that if a divisor appears twice (for example, 64 = 8*8), you only include the divisor in the sum once. Is that what you want?

[jkmyoung]

My suggestion: Prime factorize

1. Speed.
a. Check far less numbers, as you can divide out the prime factor with each check. You only have to check as far as Min(2nd greatest prime factor, sqrt(greatest prime factor)) which is a huge time reduction.
b. Calculating the sum involves fewer operations; uses multiplication as opposed to addition.
c. Since you divide out the 2's from the beginning, you only have to check every 2nd number after 2.
2. More complicated to understand.

If you prime factorize the number into primes, p1, p2, p3, ....
Where
n = p1^i1 * p2^i2 * p3^i3 ...

All the divisors are in the form
p1^j1 * p2^j2 * p3 ^ j3 ....
where
0 <= j1 <= i1,
0 <= j2 <= j2,
....

To get the sum of the divisors, you can take each prime seperately, giving you:
[p1^(i1+1)-1]/(p1-1) * [p2^(i2+1)-1]/(p2-1) *[p3^(i3+1)-1]/(p3-1) * ....

So when you find a factor, find out how many times it goes into it.
Say the current sum of divisors is 11, and then you find 3 goes into the number. If it goes in 2 times, then change your current sum like so:

11 *= [3^(2+1) - 1]/(3-1)
=> 11 *= 8/2
=> 44

Note ^ stands for exponent in this case, eg Math.pow or whatever you have to use (although it's not necessary if you do it smartly.)
===
In summary, find the prime factors of the number, and divide them out from the number, so you don't have to deal with them anymore. If you use this method, you shouldn't add both the factor and the opposite divisor like you are doing now. Can show a better example if you want, but it will take some room, and it's not worth it if you don't want to use this method.
====

[donbock]

A brute force technique for finding all the combinations of the prime factors is illustrated by the following example:

Consider the number 24. Its prime factors are 3, 2, 2, and 2. Build a table like this:

3 2 2 2 |
--------+----
0 0 0 0 |  1
0 0 0 1 |  2
0 0 1 0 |  2
...
0 1 1 1 |  8
1 0 0 0 |  3
...
1 1 1 0 | 12
1 1 1 1 | 24

where the left N columns (where N is the number of prime factors) count in binary from 0 to 2^N-1; and the rightmost column is computed by starting with "1" and multiplying by each prime factor whose counting bit is 1.

Discard all duplicates and you have a list of all the factors of the starting number.

[jkmyoung]

Just to show the algorithm works on 24:
Start with 1 as a factor.
n = 24
i = 2! i divides n.
n => 12 (2^1)
n => 6 (2^2)
n => 3 (2^3)

This gives us (1, 2, 4, 8)
Using the formula, we go:
(2^4 -1)/(2-1) = 15/1 = 15
1 * 15 = 15. So the sum so far is 15. = 1 + 2 + 4 + 8. Check!

Next i = 3. 3 divides n.
n=> 1 (3^1)
Ok, so we have factors
(1, 2, 4, 8) * 1, and (1, 2, 4, 8) * 3
(3^2 - 1)/(3-1) = 8 /2 = 4
15 * 4 = 60
The sum of factors of 24 is 60.
Checking, we have factors
1, 2, 4, 8, 3, 6, 12, 24, rearrange to:
1, 2, 3, 4, 6, 8, 12, 24 => 60.

adv/disadv:
+ Don't have to check for duplicates.
- Complexity.