检查Python中数组元素是否可以通过乘以给定的素数使其相等

假设我们有两个数组，一个是nums，另一个是primes。我们必须检查是否可以通过乘以primes数组中的一个或多个素数来使nums的所有元素相等。

因此，如果输入类似于nums = [25, 100] primes = [2, 5]，则输出将为True，因为我们可以将25乘以2两次以获得100，然后所有元素都相同。

为了解决这个问题，我们将遵循以下步骤：

• lcm_arr := nums中所有元素的最小公倍数
• 对于i从0到nums大小-1，执行：
  • val := lcm_arr/nums[i]
  • 如果primes的大小不为0且val不为1，则：
    • 当val mod primes[0]为0时，执行：
      • val := val/primes[j]
  • 如果val不等于1，则：
    • 返回False
• 返回True

示例

让我们看看下面的实现以更好地理解：

from math import gcd
def array_lcm(nums):
   ans = nums[0]
   for i in range(1,len(nums)):
      ans = (nums[i]*ans)/gcd(nums[i], ans)
   return ans
def solve(nums, primes):
   lcm_arr = array_lcm(nums)
   for i in range(len(nums)):
      val = lcm_arr/nums[i]
      for j in range(len(primes) and val != 1):
         while (val % primes[j] == 0):
            val = val/primes[j]
      if (val != 1):
         return False
   return True
nums = [25, 100]
primes = [2, 5]
print(solve(nums, primes))

输入

[25, 100], [2, 5]

输出

True

Arnab Chakraborty

更新于：2021年1月18日

115 次浏览

开启你的职业生涯

完成课程获得认证

开始学习