Why can we check the summation of all prime divisors till n just by iterating through the square root of n?

[coderaashir]

The algorithm goes something like this:
1) input n
2) int sum is 0
2) for x: 1 to sqrt(n)
3) if x is equal to n / x then add x
4) else if n % x == 0 then add x + n / x
5) return sum

The 3rd step checks if x is the square root
Why does this work? Is there a name for this algorithm?

Any help would be appreciated. Thanks in advance

[closed account EzCoLyTq]

Hi,

Suppose you input n = 9 (Step 1), and sum = 0 (Step 2)

You begin a number of loops with the initial value of (x = 1) (in Step 3) with the value of (x) increased one by one after the completion of each loop in step 4 (the program will then jump to Step 3) until the value of (x) equals to the sqrt(n) or the square root value of (n) - meaning (x = n = 3). When the condition is fulfilled, the loop will break (the program will jump to Step 5) and the final value (sum) is returned.

Note : (!=) in cplusplus means "not equal"

For example :
+ Step 1 & 2 done, proceed to Step 3
+ Initiate the loops (once) :
x = 1, sprt(n) = 3

+ Loop 1 (x = 1) :
x != sprt(n), so execute Step 4, then jump to Step 3, then increase (x) by 1

+ Loop 2 (x = 2) :
x != sprt(n), so execute Step 4, then jump to Step 3, then increase (x) by 1

+ Loop 3 (x = 3) :
x = sprt(n), so break the loop, jump to Step 5, and return the value (sum) <program ends>

The step 3 is effective because the step involves increasing the value of (x) one by one prior to checking (if x = sqrt(n)). Regardless of the value of (n), it will continue to loop until it reacts (by breaking the loop and jumping to Step 5) when (x = sqrt(n)). For instance, if you input n = 25 then the loop will end when (x = 5)

(The algorithm will only work if sqrt(n) is an integer though)

Hope this helps.

Edit : Btw, do you bring your code with you?

[coderaashir]

I get How the code works, I know it works too. I'm trying to figure out WHY the code works, like the logic behind the algorithm, as it's an optimisation over the normal O(n) algorithm that checks all divisors till n.

Yeah, I didn't have access to my laptop, here's the function:

int sum_of_divisors(int n){ 
int sum = 0; 

for(int i = 1; i <= sqrt(n); i++){ 
if(i == n / i) sum += i; 
else if(!(n % i)) sum += i + (n /  i);  // this step trips me up 
} 
return sum; 
} 

Note: This includes non- trivial divisors. (1 and n itself.)

Thanks for your response

[closed account EzCoLyTq]

int sum_of_divisors(int n)
{ 
       int sum = 0; 
       for(int i = 1; i <= sqrt(n); i++)
       { 
              if(i == n / i) sum += i; 
              elseif (n % i == 0) sum += i + (n /  i); // this step trips me up
       } 
       return sum; 
 }

else if n % x == 0 then add x + n / x

[coderaashir]

Yeah, my bad. I edited.

[closed account EzCoLyTq]

To your question :
if(!(n % i)) sum += i + (n / i);

This means if the result (the remainder) of the divide operation (n % i) is zero, (sum) value will be increased by the total of (i) with the result (the quotient) of the divide operation (n / i).

Note that (a / b) will results in a quotient and (a % b) will results in a remainder of the operation (integers only)

Does this fully answer your question?

[coderaashir]

No.
I know basic C++ syntax, and the modulo operator and the division operator.
But I don't get the algorithm, and why it returns the sum of all divisors of n. Let me further explain:

Here's a code that I would typically use to find the sum of divisors of n:

int sum_of_divisors(int n){
int sum = 0; 

for(int i =1; i <= n; i++) if( !(n % i) ) sum += i;  

return sum; 
} 

The above code has an O(n) running time.

Why does it work? Because we check every i which divides n evenly and add it to the sum variable.

But in the other algorithm, we check every i till sqrt(n) which divides n evenly, and if it isn't the square root then we add it to the sum variable along with n / i. If it is the square root, we only add i. Why does that work? What's the mathematics behind it?

That's my question. I don't have any confusion with the syntax.

[Duthomhas]

Because you cannot have an integer divisor of n > √n ([edit]without finding the corresponding term[/edit]).

Consider the divisors of, say, 24, calculated using your standard grade-school method (trying 1, then 2, then 3, etc):

    24  12   8   6 
     1   2   3   4

After four, you try five (and fail), then you would try six -- but six has already been determined as a divisor of 24 (with 24%4==0).

Hope this helps.

[coderaashir]

Thanks that helped. I was thinking of it the wrong way.