Find k-th smallest divisor of a number in C++

In this article, you will have a positive integer and you have to find its k-th smallest divisor. Let’s take two integers num and k for the same.

The divisor of num is any such natural number, that num can be divided by it without giving the remainder.

Input: We will input two integers num and k.

Some examples:

If, num = 6     k=2
The 2nd smallest divisor = 2

If, num = 15     k=3
The 3rd smallest divisor = 5

There are multiple ways to find k-th smallest divisor based on Time complexity

(I) Time Complexity = N

This is done by going through all the N numbers from 1 to N and checking if they are divisor or not. If the number is divisor then we will append it to the vector. So that we can get the result. In the end, we will sort the vector in ascending order if required and return the kth value in the vector. The code is :-

#include<bits/stdc++.h>
using namespace std;
int main()
{
   //Initialising the number
   int num; 
   //Taking input                       
   cin>>num;                         
   vector<int> divisor;
   //Finding all diviser using for loop     
   for(int i=1;i<=(num);i++)          
   {
       if(num%i==0)
       {
           divisor.push_back(i); 
       }
   }
   //initialising k-th number
   int k;                          
   cin>>k;
   cout<<divisor[k-1];
}
Input: num=6, k=3
Output : 3

(II) Time-efficient approach —>  Time Complexity = √N

In this approach, we insert a number in two vectors divisor1 and divisor2. In divisor1 we insert numbers between 1 to sqrt(N) and in divisor2 we insert a number between sqrt(N)+1 to N. Finally, reverse the divisor2 vector and return the kth element’s value from any of the vectors in which it is present. The code is:-

#include<bits/stdc++.h> 
using namespace std; 
int main() {
   //Initialising the number 
   int num;
   //Taking input 
   cin>>num; 
   vector<int> divisor1;
   vector<int> divisor2; 
   //Finding all diviser using for loop 
   for(int i=1;i<=sqrt(num);i++) 
   { 
      if(num%i==0) 
      { 
         divisor1.push_back(i);
         if(i!=sqrt(num))
         {
             divisor2.push_back(num/i);
         }  
      }  
    }  
    //initialising k-th number 
    int k; 
    cin>>k;
    reverse(divisor2.begin(), divisor2.end()); 
    if ( k > (divisor1.size() + divisor2.size())) 
        cout << "Wrong input" ; 
    else
    { 
        if(k <= divisor1.size()) 
            cout<<divisor1[k-1]; 
        else
            cout<<divisor2[k-divisor1.size()-1]; 
    } 
}
Input: num=12, k=5
Output : 6

Also read: Find the nth Term in Dragon Curve Sequence in C++

Leave a Reply

Your email address will not be published. Required fields are marked *