Divine Divisors Problem | C++

January 3, 2022

Divine Divisors Problem 

Divine Divisors Problem is one of the easy problems asked in TCS – Codevita. Here is the c++ program to solve the Divine divisor problem where we need to find the divisors of a given number and print them in increasing order. To solve this problem we will use c++ programing language and search for all the divisors of the number and sort them to print them in increasing order. The difficulty level of this problem is low and can be solved easily here is the c++ solution for the problem.

 
Divine Divisors C++

Problem Statement

Print a line containing all the divisors in increasing order separated by space. Include 1 and The number itself.

Input Format: The first line of input contains an integer ‘N’ denoting the number.

Output Format: Print a line containing all the divisors in increasing order separated by space.

Constraints:
1 <= N <= 10^8

S.no Input Output
1 10 1 2 5 10

Brute Force Approach

  • Take all the numbers Possible from 1 to N.
  • See If N is divisible by the numbers.
  • If yes, print the numbers, space separated.

Time Complexity : O(N)

The code to implement this:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    if(n%i==0) cout<<i<<" ";
    return 0;
}

Optimised Approach

  • Take all the numbers Possible from 1 to Square root of N.
  • See If N is divisible by the numbers.
  • If yes, store the number, and also N/the number.
  • Because for every number there will be another number.
  • Atlast check if the number is perfect square, then you will have included the square root twice.

Time Complexity : O( Sqrt(N) )

Divine Divisors

The code to implement this:

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	cin>>n;
	vector<int> v1,v2;
	for(int i=1;i*i<=n;i++) 
	if(n%i==0) 
	{
		v1.push_back(i);
		if(i*i!=n) v2.push_back(n/i);
	}
	for(auto i:v1) cout<<i<<" ";
	reverse(v2.begin(),v2.end());
	for(auto i:v2) cout<<i<<" ";
	return 0;
}

Java

To find the solution of Divine Divisors Problem in Java Programming language click on the button below:

Java

C

To find the solution of Divine Divisors Problem in C Programming language click on the button below:

C

 

Python

To find the solution of Divine Divisors Problem in Python Programming language click on the button below:

Python

Article is contributed by Rahit Saha