Pythonの要素のリストの最大公約数を見つけるプログラム

numsという要素のリストがあるとすると、各整数を除算する最大の正の値を見つける必要があります。

したがって、入力がnums =[15、81、78]の場合、出力は3になります。これは、3が15、81、および78すべてを除算する最大の整数であるためです。

これを解決するには、次の手順に従います-

• numsのサイズが1と同じ場合、

  • nums [0]

    を返します

• div：=nums[0]とnums[1]のgcd）

• numsのサイズが2と同じ場合、

  • divを返す

• 範囲1からnums-2のサイズのiの場合、実行

  • div：=divとnumsのgcd[i + 1]

  • divが1と同じ場合、

    • divを返す

• divを返す

例

理解を深めるために、次の実装を見てみましょう

from math import gcd
def solve(nums):
   if len(nums) == 1:
      return nums[0]

   div = gcd(nums[0], nums[1])

   if len(nums) == 2:
      return div

   for i in range(1, len(nums) - 1):
      div = gcd(div, nums[i + 1])
      if div == 1:
         return div

return div

nums = [15, 81, 78]
print(solve(nums))

入力

[15, 81, 78]

出力

3