Imprime el k-ésimo factor común de dos números

Dados tres números x, y y k, encuentre el k-ésimo factor común de x y y. Imprime -1 si hay menos de k factores comunes de x e y. 
Ejemplos: 
 

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

Encontramos que el menor de dos números como factor común no puede ser mayor que el número menor. Luego ejecutamos un bucle desde 1 hasta el número más pequeño. Para cada número i, comprobamos si es un factor común. En caso afirmativo, incrementamos el recuento de factores comunes. 
A continuación se muestra la implementación: 
 

// 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 findKCF(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 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.

# 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# 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 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.
?>

<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>

Producción : 

4

Complejidad temporal: O(n) donde n es el más pequeño entre (x,y)

Espacio auxiliar: O(1)

Este artículo es una contribución de Afzal Ansari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.