The kth factor of n python

Given two positive integers N and K, the task is to print the Kth largest factor of N.  

Input: N = 12, K = 3
Output: 4
Explanation: The factors of 12 are {1, 2, 3, 4, 6, 12}. The largest factor is 12 and the 3rd largest factor is 4.

Input: N = 30, K = 2
Output: 15
Explanation: The factors of 30 are {1, 2, 3, 5, 6, 10, 15, 30} and the 2nd largest factor is 15.

Approach: The idea is to check for each number in the range [N, 1], and print the Kth number that divides N completely.

Iterate through the loop from N to 0. Now, for each number in this loop:

• Check if it divides N or not.
• If N is divisible by the current number, decrement the value of K by 1.
• When K becomes 0, this means that the current number is the Kth largest factor of N.
• Print the answer according to the above observation.

Below is the implementation of the above approach:

C

#include

int KthLargestFactor(int N, int K)

{

    for (int i = N; i > 0; i--) {

        if (N % i == 0)

            K--;

        if (K == 0) {

            return i;

        }

    }

    return -1;

}

int main()

{

    int N = 12, K = 3;

    printf("%d", KthLargestFactor(N, K));

    return 0;

}

C++

#include

using namespace std;

int KthLargestFactor(int N, int K)

{

    for (int i = N; i > 0; i--) {

        if (N % i == 0)

            K--;

        if (K == 0) {

            return i;

        }

    }

    return -1;

}

int main()

{

    int N = 12, K = 3;

    cout << KthLargestFactor(N, K);

}

Java

import java.io.*;

class GFG {

    static int KthLargestFactor(int N, int K)

    {

        for (int i = N; i > 0; i--) {

            if (N % i == 0)

                K--;

            if (K == 0) {

                return i;

            }

        }

        return -1;

    }

    public static void main(String[] args)

    {

        int N = 12, K = 3;

        System.out.println(KthLargestFactor(N, K));

    }

}

Python

def KthLargestFactor(N, K):

    for i in range(N, 0, -1):

        if N % i == 0:

            K -= 1

        if K == 0:

            return i

    return -1

N = 12

K = 3

print(KthLargestFactor(N, K))

C#

using System;

using System.Collections.Generic;

class GFG{

static int KthLargestFactor(int N, int K)

{

    for (int i = N; i > 0; i--) {

        if (N % i == 0)

            K--;

        if (K == 0) {

            return i;

        }

    }

    return -1;

}

public static void Main()

{

    int N = 12, K = 3;

    Console.Write(KthLargestFactor(N, K));

}

}

Javascript

Time Complexity: 

Efficient Approach: The problem can be solved in an optimized way in sqrt(n) complexity by using the fact that factors of any number remain in the form of pairs. In other words, if i is a factor of number n then n/i  will also be a factor of n. So in order to find all the factors of the number we need to check for factors till sqrt(n) and their corresponding pairs. A similar type of approach is used in the article: find divisors of natural numbers.

Illustration: 
If n = 80, then all the various pairs of divisors possible are: (1,80), (2,40), (4,20), (5,16), (8,10). Hence in order to store all the factors of 80, we will iterate the loop from 1 to √80 ≈ 8 and store the factors in the range(which includes 1,2,4,5,8 here in this case). After this, we run a reverse loop and store the pairs of these previous factors (which will give 10, 16, 20, 40, and 80). Here we are running a reverse loop so that we can get the pairs in increasing order. In this way, we will get all the factors which include {1, 2, 4, 5, 8, 10, 16, 20, 40, and 80}.

Approach:

1. Initialize a vector to store the elements in increasing order.
2. First, iterate a loop from 1 to sqrt(n) and store all the factors.
3. Then iterate the loop in reverse order and for each factor store its corresponding pair. So if i is the factor then store n/i.
4. If the size of the vector is greater or equal to k then return the kth largest factor(which will be v[v.size()-k] as the vector v is in increasing order).
5. If k elements do not exist that means there is no kth largest factor and hence return -1.

Handling the corner cases:
A corner case will arise when any factor is exactly equal to sqrt(n). For example, if n=100, then in this case 10 will be a factor of the number, and also its corresponding pair is 10 as (10*10=100). So in this case 10 will be taken two times. In order to tackle this case, we use an if statement between two loops and remove the issue by considering this factor only one time.

Below is the implementation of the above approach:

C++

#include

using namespace std;

int KthLargestFactor(int n, int k)

{

    vector<int> v;

    int i;

    for (i = 1; i * i <= n; i++) {

        if (n % i == 0)

            v.push_back(i);

    }

    if (i * i == n) {

        i--;

    }

    for (; i >= 1; i--) {

        if (n % i == 0)

            v.push_back(n / i);

    }

    if (k <= v.size()) {

        return v[v.size() - k];

    }

    else

        return -1;

}

int main()

{

    int N = 12, K = 3;

    cout << KthLargestFactor(N, K);

}

Time Complexity: O(sqrt(n)) 
Auxiliary Space: O(m) where m is the total number of factors of n.

What is KTH factor?

How do you find the KTH largest factor of a number n?

How do you find the nth factor?

How do you find the largest factor of a number in Python?