Comprobar si un número es divisible por todos los divisores primos de otro número

Dados dos números enteros. Necesitamos encontrar si el primer número x es divisible por todos los divisores primos de y. 
Ejemplos: 
 

Input  : x = 120, y = 75
Output : Yes
Explanation :
120 = (2^3)*3*5
75  = 3*(5^2)
120 is divisible by both 3 and 5 which 
are the prime divisors of 75. Hence, 
answer is "Yes".

Input  :  x = 15, y = 6
Output : No
Explanation : 
15 = 3*5.
 6 = 2*3,
15 is not divisible by 2 which is a 
prime divisor of 6. Hence, answer 
is "No".

Una solución simple es encontrar todos los factores primos de y. Para cada factor primo, comprueba si divide x o no. 
Una solución eficiente se basa en los siguientes hechos. 
1) si y == 1, entonces no hay divisores primos. Por lo tanto, la respuesta es «Sí» 
2) Encontramos MCD de x e y. 
      a) Si GCD == 1, entonces claramente no hay divisores comunes de x e y, por lo que la respuesta es «No». 
      b) Si MCD > 1, el MCD contiene divisores primos que también dividen a x. Ahora, tenemos todos los divisores primos únicos si y solo si y/GCD tiene dicho divisor primo único. Entonces tenemos que encontrar la unicidad para el par (x, y/GCD) usando la recursividad.
 

// CPP program to find if all prime factors
// of y divide x.
#include <bits/stdc++.h>
using namespace std;
 
// Returns true if all prime factors of y
// divide x.
bool isDivisible(int x, int y)
{
    if (y == 1)
        return true;
 
    if (__gcd(x, y) == 1)
        return false;
    return isDivisible(x, y / gcd);
}
 
// Driver Code
int main()
{
    int x = 18, y = 12;
    if (isDivisible(x, y))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

// Java program to find if all
// prime factors of y divide x.
class Divisible
{
    public static int gcd(int a, int b) {
      return b == 0 ? a : gcd(b, a % b); }
     
    // Returns true if all prime factors
    // of y divide x.
    static boolean isDivisible(int x, int y)
    {
        if (y == 1)
            return true;
             
        int z = gcd(x, y);
     
        if (z == 1)
            return false;
     
        return isDivisible(x, y / z);
    }
 
    // Driver program to test above functions
    public static void main(String[] args)
    {
        int x = 18, y = 12;
        if (isDivisible(x, y))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
// This code is contributed by Prerna Saini

# python program to find if all
# prime factors of y divide x.
 
def gcd(a, b):
    if(b == 0):
        return a
    else:
        return gcd(b, a % b)
     
# Returns true if all prime
# factors of y divide x.
def isDivisible(x,y):
     
    if (y == 1):
        return 1
 
    z = gcd(x, y);
     
    if (z == 1):
        return false;
     
    return isDivisible(x, y / z);
 
# Driver Code
x = 18
y = 12
if (isDivisible(x, y)):
    print("Yes")
else:
    print("No")
 
# This code is contributed by Sam007

// C# program to find if all
// prime factors of y divide x.
using System;
 
class GFG {
     
    public static int gcd(int a, int b)
    {
        return b == 0 ? a : gcd(b, a % b);
    }
     
    // Returns true if all prime factors
    // of y divide x.
    static bool isDivisible(int x, int y)
    {
        if (y == 1)
            return true;
             
        int z = gcd(x, y);
     
        if (z == 1)
            return false;
     
        return isDivisible(x, y / z);
    }
 
    // Driver program to test above functions
    public static void Main()
    {
        int x = 18, y = 12;
         
        if (isDivisible(x, y))
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No");
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP program to find if all
// prime factors of y divide x.
 
function gcd ($a, $b)
{
    return $b == 0 ? $a :
        gcd($b, $a % $b);
}
 
// Returns true if all prime
// factors of y divide x.
function isDivisible($x, $y)
{
    if ($y == 1)
        return true;
     
    $z = gcd($x, $y);
     
    if ($z == 1)
        return false;
     
    return isDivisible($x, $y / $z);
}
 
// Driver Code
$x = 18;
$y = 12;
if (isDivisible($x, $y))
    echo "Yes";
else
    echo "No";
 
// This code is contributed by Sam007
?>

<script>
 
// Javascript program to find if all
// prime factors of y divide x.
 
function gcd(a , b) {
  return b == 0 ? a : gcd(b, a % b); }
 
// Returns true if all prime factors
// of y divide x.
function isDivisible(x , y)
{
    if (y == 1)
        return true;
         
    var z = gcd(x, y);
 
    if (z == 1)
        return false;
 
    return isDivisible(x, y / z);
}
 
// Driver program to test above functions
 
var x = 18, y = 12;
if (isDivisible(x, y))
    document.write("Yes");
else
    document.write("No");
 
// This code is contributed by Amit Katiyar
 
</script>

Producción : 

Yes

Complejidad de tiempo: la complejidad de tiempo para calcular GCD es O (log min (x, y)), y la recursividad terminará después de los pasos de log y porque la estamos reduciendo por un factor mayor que uno. Complejidad total del tiempo: O(log ² y)
Espacio auxiliar: O(log min(x, y))

Este artículo es una contribución de Aarti_Rathi y Harsha Mogali . 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.