Compruebe si el LCM de los elementos de la array es divisible por un número primo o no

Dado un arreglo y un número k, la tarea es encontrar si el LCM del arreglo es divisible por k o no.
Ejemplos: 
 

Input : int[] a = {10, 20, 15, 25}
              k = 3
Output : true

Input : int[] a = {24, 21, 45, 57, 36};
              k = 23;
Output : false

Una solución simple es primero encontrar LCM de los elementos de la array , luego verificar si LCM es divisible por k o no.
Aquí, sin calcular el MCM del número, podemos encontrar que el MCM de una array de números es divisible por un número primo k o no. Si cualquier número de la array es divisible por el número primo k, entonces el MCM del número también es divisible por el número primo k.
 

// C++ program to find LCM of
// array of number is divisible
// by a prime number k or not
#include<iostream>
using namespace std;
 
// Function to check any number of
// array is divisible by k or not
bool func(int a[], int k, int n)
{
    // If any array element is divisible
    // by k, then LCM of whole array
    // should also be divisible.
    for (int i = 0; i < n; i++)
        if (a[i] % k == 0)
        return true;
    return false;
}
 
// Driver Code
int main()
{
    int a[] = {14, 27, 38, 76, 84};
    int k = 19;
    bool res = func(a, k, 5);
    if(res)
    cout<<"true";
    else
    cout<<"false";
    return 0;
}
 
// This code is contributed
// by Mr. Somesh Awasthi

// Java program to find LCM of
// array of number is divisible
// by a prime number k or not
import java.lang.*;
import java.util.*;
 
class GFG
{
    // Function to check any number
    // of array is divisible by k or not
    static boolean func( int a[], int k)
    {
        // If any array element is divisible
        // by k, then LCM of whole array
        // should also be divisible.
        for (int i = 0; i < a.length; i++)
            if (a[i] % k == 0)
            return true;
        return false;
    }
 
    // Driver Code
    public static void main(String args[])
    {
        int[] a = {14, 27, 38, 76, 84};
        int k = 19;
        boolean res = func(a, k);
        System.out.println(res);
    }
}

# Python 3 program to find LCM
# of array of number is divisible
# by a prime number k or not
 
 
# Function to check any number of
# array is divisible by k or not
def func( a, k, n) :
     
    # If any array element is
    # divisible by k, then LCM
    # of whole array should also
    # be divisible.
    for i in range(0, n) :
        if ( a[i] % k == 0):
            return True
 
 
# Driver Code
a = [14, 27, 38, 76, 84]
k = 19
res = func(a, k, 5)
 
if(res) :
    print("true")
else :
    print("false")
     
 
 
# This code is contributed
# by Nikita Tiwari.

// C# program to find LCM of array
// of number is divisible by a prime
// number k or not
using System;
 
class GFG
{
     
    // Function to check any number of
    // array is divisible by k or not
    static bool func(int []a, int k)
    {
         
        // If any array element is
        // divisible by k, then LCM
        // of whole array should also
        // be divisible.
        for (int i = 0; i < a.Length; i++)
            if (a[i] % k == 0)
            return true;
        return false;
    }
 
    // Driver code
    public static void Main()
    {
        int []a = {14, 27, 38, 76, 84};
        int k = 19;
        bool res = func(a, k);
        Console.Write(res);
    }
}
 
// This code is contributed by nitin mittal.

<?php
// PHP program to find LCM of
// array of number is divisible
// by a prime number k or not
 
// Function to check any number of
// array is divisible by k or not
function func( $a, $k, $n)
{
    // If any array element is divisible
    // by k, then LCM of whole array
    // should also be divisible.
    for ($i = 0; $i < $n; $i++)
        if ($a[$i] % $k == 0)
        return true;
    return false;
}
 
// Driver Code
$a = array(14, 27, 38, 76, 84);
$k = 19;
$res = func($a, $k, 5);
 
if($res)
echo"true";
else
echo"false";
 
// This code is contributed by nitin mittal
?>

<script>
// javascript program to find LCM of
// array of number is divisible
// by a prime number k or not
 
    // Function to check any number
    // of array is divisible by k or not
    function func(a , k)
    {
     
        // If any array element is divisible
        // by k, then LCM of whole array
        // should also be divisible.
        for (let i = 0; i < a.length; i++)
            if (a[i] % k == 0)
                return true;
        return false;
    }
 
    // Driver Code
     
        let a = [ 14, 27, 38, 76, 84 ];
        var k = 19;
        let res = func(a, k);
        document.write(res);
 
 
// This code is contributed by todaysgaurav
</script>

Producción : 
 

 true

Complejidad temporal: O(n) 
Espacio auxiliar: O(1)

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