Print the kth common factor of two numbers
Given three numbers x, y and k, find the k’th common factor of x and y. Print -1 if there are less than k common factors of x and y.
Examples :
Input : x = 20, y = 24 k = 3 Output : 4 Common factors are 1, 2, 4, ... Input : x = 4, y = 24 k = 2 Output : 2 Input : x = 22, y = 2 k = 3 Output : -1
We find the smaller of two numbers as common factor cannot be greater than the smaller number. Then we run a loop from 1 to the smaller number. For every number i, we check if it is a common factor. If yes, we increment count of common factors.
Below is the Implementation :
C++
// C++ program to find kth common factor // of two numbers #include<iostream> using namespace std; // Returns k'th common factor of x and y. int findKHCF( int x, int y, int k) { // Find smaller of two numbers int small = min(x, y); // Count common factors until we either // reach small or count becomes k. int count = 1; for ( int i=2; i<=small; i++) { if (x % i==0 && y % i == 0) count++; if (count == k) return i; } // If we reached small return -1; } // Driver code int main() { int x = 4, y = 24, k = 3; cout << findKHCF(x, y, k); return 0; } |
Java
// Java program to find kth // common factor of two numbers import java.lang.*; class GFG { // Returns k'th common factor of x and y. static int findKHCF( int x, int y, int k) { // Find smaller of two numbers int small = Math.min(x, y); // Count common factors until we either // reach small or count becomes k. int count = 1 ; for ( int i = 2 ; i <= small; i++) { if (x % i == 0 && y % i == 0 ) count++; if (count == k) return i; } // If we reached small return - 1 ; } // Driver code public static void main(String[] args) { int x = 4 , y = 24 , k = 3 ; System.out.print(findKHCF(x, y, k)); } } // This code is contributed by Anant Agarwal. |
Python3
# Python program to find # kth common factor # of two numbers # Returns k'th common # factor of x and y. def findKHCF(x,y,k): # Find smaller of two numbers small = min (x, y) # Count common factors # until we either # reach small or count # becomes k. count = 1 for i in range ( 2 ,small + 1 ): if (x % i = = 0 and y % i = = 0 ): count = count + 1 if (count = = k): return i # If we reached small return - 1 # Driver code x = 4 y = 24 k = 3 print (findKHCF(x, y, k)) # This code is contributed # by Anant Agarwal. |
C#
// C# program to find kth // common factor of two numbers using System; class GFG { // Returns k'th common factor of x and y. static int findKHCF( int x, int y, int k) { // Find smaller of two numbers int small = Math.Min(x, y); // Count common factors until we either // reach small or count becomes k. int count = 1; for ( int i = 2; i <= small; i++) { if (x % i == 0 && y % i == 0) count++; if (count == k) return i; } // If we reached small return -1; } // Driver code public static void Main() { int x = 4, y = 24, k = 3; Console.Write(findKHCF(x, y, k)); } } // This code is contributed by Nitin Mittal. |
PHP
<?php // PHP program to find kth // common factor of two numbers // Returns k'th common // factor of x and y. function findKCF( $x , $y , $k ) { // Find smaller of two numbers $small = min( $x , $y ); // Count common factors until we either // reach small or count becomes k. $count = 1; for ( $i = 2; $i <= $small ; $i ++) { if ( $x % $i == 0 && $y % $i == 0) $count ++; if ( $count == $k ) return $i ; } // If we reached small return -1; } // Driver code $x = 4; $y = 24; $k = 3; echo findKCF( $x , $y , $k ); // This code is contributed by nitin mittal. ?> |
Javascript
<script> // Javascript program to find kth // common factor of two numbers // Returns k'th common factor of x and y. function findKHCF(x, y, k) { // Find smaller of two numbers let small = Math.min(x, y); // Count common factors until we either // reach small or count becomes k. let count = 1; for (let i = 2; i <= small; i++) { if (x % i == 0 && y % i == 0) count++; if (count == k) return i; } // If we reached small return -1; } // Driver code let x = 4, y = 24, k = 3; document.write(findKHCF(x, y, k)); </script> |
Time complexity: O(n) where n is smallest among (x,y)
Auxiliary space: O(1)