Modifique la array de modo que la array no contenga ningún divisor común que no sea 1

Dada una array arr[] que consta de N enteros y un entero X , la tarea es verificar si es posible modificar la array de modo que la array no contenga ningún divisor común que no sea 1 , dividiendo repetidamente cualquier elemento de array de la array por cualquiera de sus divisores d (d ≤ X ). Si es posible modificar la array para que satisfaga las condiciones dadas, imprima «Sí» . De lo contrario, escriba “No” .

Ejemplos:

Entrada: arr[] = {6, 15, 6}, X = 6
Salida:
Sí 
2 5 2
Explicación:
Operación 1: Dividir arr[0] entre 3 (ya que 3 ≤ 6) modifica arr[] a { 2, 15 , 6 }.
Operación 2: Dividir arr[1] por 5 (Ya que 5 ≤ 6) modifica arr[] a { 2, 3, 6 }. 
Por lo tanto, MCD de la array = MCD({2, 3, 6}) = 1, lo que significa que la array no tiene otro divisor común que no sea 1, que es la condición requerida.

Entrada: arr[] = {10, 20, 30}, X = 4
Salida: No

Enfoque: La idea es usar el MCD de Euclides para encontrar el MCD de la array dada . Esto da todos los factores comunes de los elementos de la array. Al eliminar todos estos factores, no queda ningún factor común. Por lo tanto, se puede generar una array de este tipo. De lo contrario, no es posible generar tal array.

Siga los pasos a continuación para resolver el problema:

1. Inicialice una variable, digamos G, para almacenar el GCD de la array dada .
2. Recorra la array arr[] y calcule el GCD y guárdelo en una variable, digamos G .
3. Iterar sobre el rango [2, X] y verificar si G tiene un divisor mayor que X o no.
4. Si se encuentra que es cierto, escriba “No” . De lo contrario, escriba «Sí».
5. De lo contrario, imprima los elementos de la array después de modificar la array dividiendo todos los elementos por G .

A continuación se muestra la implementación del enfoque anterior: 

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if it is possible
// to modify the array such that
// there is no common factor between
// array elements except 1
void checkCommonDivisor(int arr[],
                        int N, int X)
{
    // Stores GCD of the array
    int G = 0;
 
    // Calculate GCD of the array
    for (int i = 0; i < N; i++) {
        G = __gcd(G, arr[i]);
    }
 
    int copy_G = G;
 
    for (int divisor = 2;
         divisor <= X; divisor++) {
 
        // If the current divisor
        // is smaller than X
        while (G % divisor == 0) {
 
            // Divide GCD by the
            // current divisor
            G = G / divisor;
        }
    }
 
    // If possible
    if (G <= X) {
        cout << "Yes\n";
 
        // Print the modified array
        for (int i = 0; i < N; i++)
            cout << arr[i] / copy_G << " ";
        cout << endl;
    }
 
    // Otherwise
    else
        cout << "No";
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 6, 15, 6 }, X = 6;
 
    // Size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    checkCommonDivisor(arr, N, X);
}

// Java program for the above approach
class GFG{
 
// Function to check if it is possible
// to modify the array such that
// there is no common factor between
// array elements except 1
static void checkCommonDivisor(int[] arr,
                               int N, int X)
{
     
    // Stores GCD of the array
    int G = 0;
 
    // Calculate GCD of the array
    for(int i = 0; i < N; i++)
    {
        G = gcd(G, arr[i]);
    }
 
    int copy_G = G;
 
    for(int divisor = 2;
            divisor <= X;
            divisor++)
    {
 
        // If the current divisor
        // is smaller than X
        while (G % divisor == 0)
        {
             
            // Divide GCD by the
            // current divisor
            G = G / divisor;
        }
    }
 
    // If possible
    if (G <= X)
    {
        System.out.println("Yes");
 
        // Print the modified array
        for(int i = 0; i < N; i++)
            System.out.print((arr[i] / copy_G) + " ");
             
        System.out.println();
    }
 
    // Otherwise
    else
        System.out.println("No");
}
 
// Calculating gcd
static int gcd(int a, int b)
{
    if (b == 0)
        return a;
         
    return gcd(b, a % b);
}
 
// Driver Code
public static void main(String[] args)
{
    int[] arr = { 6, 15, 6 };
    int X = 6;
 
    // Size of the array
    int N = arr.length;
 
    checkCommonDivisor(arr, N, X);
}
}
 
// This code is contributed by user_qa7r

# Python3 program for the above approach
import math
 
# Function to check if it is possible
# to modify the array such that
# there is no common factor between
# array elements except 1
def checkCommonDivisor(arr, N, X):
 
    # Stores GCD of the array
    G = 0
 
    # Calculate GCD of the array
    for i in range(N):
        G = math.gcd(G, arr[i])
 
    copy_G = G
 
    for divisor in range(2, X + 1):
 
        # If the current divisor
        # is smaller than X
        while (G % divisor == 0):
 
            # Divide GCD by the
            # current divisor
            G = G // divisor
 
    # If possible
    if (G <= X):
        print("Yes")
 
        # Print the modified array
        for i in range(N):
            print(arr[i] // copy_G, end = " ")
             
        print()
 
    # Otherwise
    else:
        print("No")
 
# Driver Code
if __name__ == "__main__":
 
    # Given array
    arr = [6, 15, 6]
    X = 6
 
    # Size of the array
    N = len(arr)
    checkCommonDivisor(arr, N, X)
 
# This code is contributed by ukasp

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
static int GCD(int a, int b)
{
    return b == 0 ? a : GCD(b, a % b);
}
  
// Function to check if it is possible
// to modify the array such that
// there is no common factor between
// array elements except 1
static void checkCommonDivisor(int []arr,
                               int N, int X)
{
     
    // Stores GCD of the array
    int G = 0;
 
    // Calculate GCD of the array
    for(int i = 0; i < N; i++)
    {
        G = GCD(G, arr[i]);
    }
 
    int copy_G = G;
 
    for(int divisor = 2;
            divisor <= X;
            divisor++)
    {
         
        // If the current divisor
        // is smaller than X
        while (G % divisor == 0)
        {
             
            // Divide GCD by the
            // current divisor
            G = G / divisor;
        }
    }
 
    // If possible
    if (G <= X)
    {
        Console.WriteLine("Yes");
 
        // Print the modified array
        for(int i = 0; i < N; i++)
            Console.Write(arr[i] / copy_G + " ");
             
        Console.Write("\n");
    }
 
    // Otherwise
    else
        Console.WriteLine("No");
}
 
// Driver Code
public static void Main()
{
     
    // Given array
    int []arr = { 6, 15, 6 };
    int X = 6;
 
    // Size of the array
    int N = arr.Length;
 
    checkCommonDivisor(arr, N, X);
}
}
 
// This code is contributed by bgangwar59

<script>
// javascript program for the above approach   
// Function to check if it is possible
    // to modify the array such that
    // there is no common factor between
    // array elements except 1
    function checkCommonDivisor(arr , N , X) {
 
        // Stores GCD of the array
        var G = 0;
 
        // Calculate GCD of the array
        for (i = 0; i < N; i++) {
            G = gcd(G, arr[i]);
        }
 
        var copy_G = G;
 
        for (divisor = 2; divisor <= X; divisor++) {
 
            // If the current divisor
            // is smaller than X
            while (G % divisor == 0) {
 
                // Divide GCD by the
                // current divisor
                G = G / divisor;
            }
        }
 
        // If possible
        if (G <= X) {
            document.write("Yes<br/>");
 
            // Print the modified array
            for (i = 0; i < N; i++)
                document.write((arr[i] / copy_G) + " ");
 
            document.write();
        }
 
        // Otherwise
        else
            document.write("No");
    }
 
    // Calculating gcd
    function gcd(a , b) {
        if (b == 0)
            return a;
 
        return gcd(b, a % b);
    }
 
    // Driver Code
     
        var arr = [ 6, 15, 6 ];
        var X = 6;
 
        // Size of the array
        var N = arr.length;
 
        checkCommonDivisor(arr, N, X);
 
// This code is contributed by todaysgaurav
</script>

Yes
2 5 2

Complejidad de tiempo: O(N * logN)
Espacio auxiliar: O(1)