Part 23 of 28 in Maths - Beginner set 01  

Sum of all factors by animeshn

Problem statement

Given a number n, find the sum of all its factors.

Input

First line of input will contain T = no. of test cases. Next n lines will each contain a number n where 1<=n<=10^9

Output

For each test case, print on one single line, the sum total of all its factors.

Sample Input
4
1
2
6
9

Sample Output
1
3
12
13
1) Are you using O(n) algorithm?  Factors can be found in O(sqrt (n))

To solve the problem within the given time limits, we must observe a very important property. The observation is that, to find all the factors of a number, we need to run the loop only upto square root of the number.

This is because we can get the factors of the number which are greater than sqrt(num) simply from the numbers below sqrt(num) (Here sqrt(num) refers to square root of any number).

If a * b = c, then min(a, b) is <= sqrt(num), and max(a, b) is >= sqrt(num). If a number f is a factor of the number x, then there is a always a counterpart of the number f which is also a factor of x. The minimum of f and its counterpart will lie in the range [1, sqrt(x)] (here [] means including the boundaries) and the maximum among these two will lie in the range [sqrt(x), x] .

If we divide x by f and get f', then we can also divide x by f' to get f.

If x/f = f' , then x/f'=f. (Simple mathematics).

So, we can always say that there are even number of factors of a number except perfect squares where one of the factor and its counterpart becomes equal and as a result the total number of factors decreases by 1, making it odd finally.

So, until now, we just know that it is possible to solve the problem in O(sqrt(n)) time complexity where n is the input number.

Now, to find all the factors of a number we simply run a loop from 1 to sqrt(num). If the current loop variable is a factor of the number, then we append to the vector both the current loop variable and num/loop_var(where num is the input number, and loop_var is the current loop variable). The reason behind this is explained in the above sections.

 //Run a loop until the square root of the number
for(int i = 1; i <= sqrt(num); i++)
{
    //If the number is a perfect square, then we
    //count only 1 factor
    if(i*i == num)
    {
        factors.push_back(i);
        break;
    }
    //If the current i is a factor of the number,
    //then we add both i and 'num/i' to the list of
    //factors.
    if(num%i == 0)
    {
        factors.push_back(i);
        factors.push_back(num/i);
    }
}

As for cases of perfect squares, we cannot append both the factor and its counterpart because it will bring duplicacy in the vector. We have handled this through an 'if' statement. When factor*factor= number, we can say that the number is a perfect square, and all the factors of the number greater than the current factor have already been included in our vector. So, we only append the current number to the vector and break the loop.

Now we simply traverse the whole vector and calculate the sum of all the numbers in it and print it. Then we clear all the values in the vector to reset it.

editorial written by i_coder

#include<iostream>
#include<cstdio>
#include<cmath>
#include <vector>

using namespace std;
int main()
{
    int test_case;
    cin >> test_case; //Number of test cases
    int num;
    vector<int> factors;
    while(test_case--)
    {
        //Clear the current contents of the vector
        factors.clear();
        //Input the number
        cin >> num;
        //Run a loop until the square root of the number
        for(int i = 1; i <= sqrt(num); i++)
        {
            //If the number is a perfect square, then we
            //count only 1 factor
            if(i*i == num)
            {
                factors.push_back(i);
                break;
            }
            //If the current i is a factor of the number,
            //then we add both i and 'num/i' to the list of
            //factors.
            if(num%i == 0)
            {
                factors.push_back(i);
                factors.push_back(num/i);
            }
        }
        int sum = 0;
        for(int i = 0; i< factors.size(); i++)
        {
            sum += factors[i];
        }
        //Then we print a newline at the end of each test case.
        cout << sum  << endl;
    }
}

featured solution by i_coder



To try out your code



Sign in

Sign up