5 Best Ways to Check if LCM of Array Elements is Divisible by a Prime Number in Python

πŸ’‘ Problem Formulation: In Python, we often face the problem of finding the Least Common Multiple (LCM) of a set of numbers and then determining whether that LCM is divisible by a given prime number. For instance, given an input array [3, 4, 5] and a prime number 7, we want to find out if the LCM of the array (60) is divisible by 7 (False in this case).

Method 1: Using Math Library and Simple Iteration

This method involves using the math.gcd() function to calculate the LCM of the array elements iteratively. Next, we check if the resultant LCM is divisible by the prime number using the modulus operator.

Here’s an example:

import math

def find_lcm(num1, num2):
    return num1 * num2 // math.gcd(num1, num2)

def is_lcm_divisible_by_prime(array, prime):
    lcm = array[0]
    for element in array[1:]:
        lcm = find_lcm(lcm, element)
    return lcm % prime == 0

# Example usage
array = [3, 4, 5]
prime = 7
print(is_lcm_divisible_by_prime(array, prime))

Output: False

In this snippet, the find_lcm() function calculates the LCM of two numbers, which is then iteratively used to find the LCM of all elements in the array. After obtaining the final LCM, the function is_lcm_divisible_by_prime() checks its divisibility by the given prime number.

Method 2: Using NumPy Library

For those already using NumPy for array operations, NumPy’s lcm.reduce method can be utilized to find the LCM in a more concise manner. Once the LCM is obtained, we can check for divisibility by the prime number.

Here’s an example:

import numpy as np

def is_lcm_divisible_by_prime(array, prime):
    lcm = np.lcm.reduce(array)
    return lcm % prime == 0

# Example usage
array = np.array([3, 4, 5])
prime = 11
print(is_lcm_divisible_by_prime(array, prime))

Output: False

The function is_lcm_divisible_by_prime() leverages NumPy’s lcm.reduce() method to find the LCM of the array elements efficiently. The result is then checked for divisibility by prime.

Method 3: Using functools.reduce with a Custom LCM Function

In this method, we use the functools.reduce() function along with a custom LCM function to find the LCM of the elements in the array. Checking for divisibility by the prime number remains the same.

Here’s an example:

from functools import reduce
import math

def find_lcm(num1, num2):
    return num1 * num2 // math.gcd(num1, num2)

def is_lcm_divisible_by_prime(array, prime):
    lcm = reduce(find_lcm, array)
    return lcm % prime == 0

# Example usage
array = [3, 4, 5]
prime = 13
print(is_lcm_divisible_by_prime(array, prime))

Output: False

By using reduce() from the functools module, we can apply the find_lcm() function cumulatively to the items of array to compute the LCM, which is then tested against the prime with the modulus operator.

Method 4: Using a Custom Recursive LCM Function

If you prefer not to rely on libraries, you can create a custom recursive function to compute the LCM of the array. The divisibility by the prime number can be checked in the same way as before.

Here’s an example:

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

def find_lcm(arr):
    if len(arr) == 2:
        return arr[0] * arr[1] // gcd(arr[0], arr[1])
    return find_lcm([arr[0], find_lcm(arr[1:])])

def is_lcm_divisible_by_prime(array, prime):
    lcm = find_lcm(array)
    return lcm % prime == 0

# Example usage
array = [3, 4, 5]
prime = 17
print(is_lcm_divisible_by_prime(array, prime))

Output: False

This solution computes the LCM and the GCD using recursive functions find_lcm() and gcd(), respectively. It’s a standalone approach that checks the divisibility by the prime number without requiring any external library.

Bonus One-Liner Method 5: Functional Programming with lambda

For those who enjoy the functional programming paradigm, Python allows us to combine the gcd function and reduce in a single line of code to find the LCM, followed by a prime divisibility check.

Here’s an example:

from functools import reduce
import math

array = [3, 4, 5]
prime = 19

is_lcm_divisible_by_prime = lambda arr, p: reduce(lambda x, y: x * y // math.gcd(x, y), arr) % p == 0
print(is_lcm_divisible_by_prime(array, prime))

Output: False

This lambda function encapsulates LCM computation and divisibility checking in a single expression. It makes use of reduce() and math.gcd() in a concise, although dense, format.

Summary/Discussion

  • Method 1: Using Math Library and Simple Iteration. Strengths: Clear and easy to understand. Weaknesses: Can be slower due to explicit iteration.
  • Method 2: Using NumPy Library. Strengths: Very efficient and concise for large datasets. Weaknesses: Requires the installation of the NumPy library.
  • Method 3: Using functools.reduce with a Custom LCM Function. Strengths: Elegant use of functional programming. Weaknesses: Might be less intuitive for beginners.
  • Method 4: Using a Custom Recursive LCM Function. Strengths: Does not depend on any external libraries. Weaknesses: Recursive methods can be less efficient and harder to understand.
  • Bonus Method 5: Functional Programming with lambda. Strengths: Extremely concise. Weaknesses: Less readability, which can make the code harder to maintain.