Check if LCM of array elements is divisible by a prime number or not
Given an array and a number k, the task is to find if LCM of the array is divisible by k or not.
Examples :
Input : int[] a = {10, 20, 15, 25} k = 3 Output : true Input : int[] a = {24, 21, 45, 57, 36}; k = 23; Output : false
One simple solution is to first find LCM of array elements, then check if LCM is divisible by k or not.
Here, without calculating the LCM of the number we can find that LCM of the array of number is divisible by a prime number k or not. If any number of the array is divisible by prime number k, then the LCM of the number is also divisible by prime number k.
C++
// 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
// 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
# 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#
// 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 // 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 ?> |
Javascript
<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> |
Output :
true
Time Complexity: O(n)
Auxiliary Space: O(1)