Part 25 of 28 in Maths - Beginner set 01  

Find all factors of a number by animeshn

Problem statement

Given a number, find all its factors.

Input

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

Output

For each test case, print on a single line, a space separated list of all the factors of n in increasing order. There should be no space after last factor on each line.

Sample Input
4
36
48
15
19
Sample Output
1 2 3 4 6 9 12 18 36
1 2 3 4 6 8 12 16 24 48
1 3 5 15
1 19

1) There should be no space after last integer on each line of input.

2) O(n) algorithm is not good enough. It will give you "Time Limit Exceeded"

3) Make sure the factors are printed in increasing order.

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 y, then we can also divide x by y to get f.

If x/f = y , then x/y=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.

Finally we have sorted the array in increasing order.

Now, we have to handle the case of not printing a blank (' ') after the last factor. This can be simply done by checking if the current number is the last number in the vector. If it is so, then we execute a different print statement.

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);
            }
        }
        //we sort the list of factors.
        sort(factors.begin(), factors.end());
        //In order to avoid printing space after the last number
        //we simply use a check condition.

        for(int i = 0; i< factors.size(); i++){
            if(i == factors.size() -1)
                cout << factors[i];
            else
                cout <<  factors[i] << " ";
        }
        //Then we print a newline at the end of each test case.
        cout << endl;
    }
}

featured solution by i_coder



To try out your code



Sign in

Sign up