Need more efficient program (Sum of all divisors of an integer)

[Oriol Serrabassa]

I need to make a more efficient program to sum all divisors of a number because my code exceeds time limit, however I do not know how to improve my code furthermore so I am asking for help.

I am only allowed to use iostream and cmath library/inclusion.

#include <iostream>
using namespace std;

int suma_divisors(int x) {
	int total = 0;
	for (int i = 1; i <= x/2; ++i) if (x%i == 0) total += i;
	total += x;	
	return total;
}

int main () {
	int x;
	while (cin >> x) cout << suma_divisors (x) << endl;
}

[Ciplas Plas]

FiB representing.

[lastchance]

You might be able to find factors recursively - if you split x into two smaller factors and factorise these you will be dealing with smaller numbers, so possibly faster. Maybe this will help.

Also, if x has any factors then one of them must be less than or equal to the square root of x, which gives a smaller search range than x/2.

[integralfx]

You can initialise total with x + 1, since x and 1 are always going to be factors. Then you can start the loop at i = 2.
You only need to go up to, but not including, the sqrt( x ) + 1.

Here's an improved version, albeit still a naive approach:

int sum_divisors2( const int x )
{  
    int sum{ 1 + x }, 
        sqrt_x = sqrt( x ); // this is needed a few times, so store the value rather than calling it uneccesarily
    for( int i{ 2 }; i < sqrt_x + 1; i++ ) {
        if( x % i == 0 ) 
            sum = sum + i + x/i;    // x/i is the other factor pair
    }
    
      // in case x is a perfect square, eg 25, we don't want to count 5 twice.
    if( sqrt_x * sqrt_x == x )
        return sum - sqrt_x;
    
    return sum;
}

sum_divisors( 5362 ) = 9216
elapsed = 1054.63 ms

sum_divisors2( 5362 ) = 9216
elapsed = 30.6367 ms

sum_divisors2( ) is 97.10% faster(1023.99 ms)

http://cpp.sh/7ql42

[Oriol Serrabassa]

If i use sqrt (x) I am missing more than half of divisors so just no

[integralfx]

If i use sqrt (x) I am missing more than half of divisors so just no

That's because your code only counts one of the factor pairs.

Hence this:
sum = sum + i + x/i; // x/i is the other factor pair

[Oriol Serrabassa]

Let's put as example x = 100000000
sqrt (x) = 10000
So loops stops too early to sum all divisors, ignoring all these:
12500, 15625, 16000, 20000, 25000, 31250, 32000, 40000, 50000, 62500, 78125, 80000, 100000, 125000, 156250, 160000, 200000, 250000, 312500, 390625, 400000, 500000, 625000, 781250, 800000, 1000000, 1250000, 1562500, 2000000, 2500000, 3125000, 4000000, 5000000, 6250000, 10000000, 12500000, 20000000, 25000000, 50000000, 100000000


Also, I am getting a compiler error with your program:

warning: extended initializer lists only available with -std=c++11 or -std=gnu++11

I am using C++ not C++11 (even though they are almost the same they aren't equal)

[integralfx]

Let's put as example x = 100000000
sqrt (x) = 10000
So loops stops too early to sum all divisors, ignoring all these:
12500, 15625, 16000, 20000, 25000, 31250, 32000, 40000, 50000, 62500, 78125, 80000, 100000, 125000, 156250, 160000, 200000, 250000, 312500, 390625, 400000, 500000, 625000, 781250, 800000, 1000000, 1250000, 1562500, 2000000, 2500000, 3125000, 4000000, 5000000, 6250000, 10000000, 12500000, 20000000, 25000000, 50000000, 100000000

Since 100,000,000 is a perfect square, the highest factor pair is (10,000 10,000). This means all the factors up until 10,000 have already been accounted for. For example, 12,500's pair is 8,000, but the loop goes up until 10,000 + 1. Since 8000 < 10,000, 12,500 has already been added.

warning: extended initializer lists only available with -std=c++11 or -std=gnu++11

I am using C++ not C++11 (even though they are almost the same they aren't equal)

That's because I've initialised values using the braces initialisation, which is a C++11 feature. Just initialise them how you would normally.

int sum{ 1 + x };
// becomes this:
int sum = 1 + x;

[SakurasouBusters]

int x, i, sum = 0;
cout << "Enter x : "; cin >> x;

for(i = 1; i <= x; i++)
{
    if(x % i == 0) sum += i;
}

cout << "Sum of all divisors : " << sum << endl;

[cire]

A factor of x is some whole number i which when multiplied by some whole number j yields exactly x.

When you have found an i, then j is trivially calculated by x/i. In other words, when you've found one of a pair of factors you've effectively found the other. When you find all of the factors less than the square root of x you've found enough factors to calculate the others trivially (which integralfx explains in a less verbose way above.)

[Edit: And I'd like to congratulate SakurasouBusters for supplying an algorithm even worse than that in the OP.]

[Oriol Serrabassa]

So what I am supposed to do because I do not seem to understand.

I make i = sqrt (x) and I search divisors of x until sqrt (x) and then multiply them by i?

[cire]

I make i = sqrt (x) and I search divisors of x until sqrt (x) and then multiply them by i?

In the explanation I supplied above i is a divisor of x. The square root of x is signified by "the square root of x." Perhaps you should take another look at the code supplied by integralfx and trace through the logic again.

I'll re-write it in the terms I couched it in above:

int sum_divisors2( const int x )
{
    int sum = 1+x;

    int limit = sqrt(x);

    for ( int i = 2; i < limit; ++i ) {
        if ( x % i == 0 ) {  // i is a factor ?
            int j = x / i;       // j is the other factor in the pair.
            sum += i + j;
        }
    }

    if ( x % limit == 0 ) // the case where x is a perfect square
        sum += limit;
  
    return sum; 
}

[Oriol Serrabassa]

So this is the full working code supplied by integralfx addapted to my programming style, which is noticibly faster (97% faster as he/she said).

#include <iostream>
#include <cmath>
using namespace std;

int sum_divisors(int x) {  
	int sum = 0; 
	int sqrt_x = sqrt(x);
	for (int i = 1; i <= sqrt_x; ++i) if (x%i == 0) sum += i + x/i;
    	if (sqrt_x*sqrt_x == x) return sum - sqrt_x;
    	else return sum;
}

int main () {
	int x;
	while (cin >> x) cout << sum_divisors (x) << endl;
}

[integralfx]

1. Why this condition for the loop? "i < sqrt_x +1" instead of the "i < sqrt_x" you have been saying all this time.

Probably a typo.
Consider when x = 20. √20 ≈ 4.47. Implicitly converting to an int, will truncate the decimal places, thus becoming 4. Therefore, the loop will only go until i = 3, missing the factor pair (4, 5).
Note that i < sqrt_x + 1 == i <= sqrt_x.

2. Why this line? "if (sqrt_x*sqrt_x == x) return sum - sqrt_x;"

To check if x is a perfect square. Using x = 20 and sqrt_x = 4, 4*4 != 20, so we don't need to subtract the duplicate factor.
However, when x = 25, sqrt_x = 5, 5*5 == 25, so we need to subtract the duplicate factor, 5.

sum = sum + i + x/i;
Also, you can shorten this to: sum += i + x/i;. I don't know why I didn't though...

[Oriol Serrabassa]

Sorry to make you answer those questions, I realized myself after sending the post, that's why I tweaked the code. I do not know if it is only me, but I receive posts like in a 5 minute delay.

In a few hours, I will know if my problem is accepted or not. I am almost sure it will be though. So meanwhile, I cannot mark my question as solved.