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?
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)
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:
1 2 3 4 5 6 7 8 9
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)) sum += i + (n / i); // this step trips me up
}
return sum;
}
Note: This includes non- trivial divisors. (1 and n itself.)
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;
}
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)
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:
1 2 3 4 5 6 7
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.