プログラマ-N個最小公倍数

1266 ワード
プログラマ パイ レベル2 テキストリンク

N個の最小公倍数


まず、この問題を見ると、ユークリッド弧除法のような方法が思いつかず、無知な方法で解いた.
def solution(arr):
    arr.sort()
    for i in range(arr[len(arr) - 1], 10 ** 16):
        minimum = True
        for j in arr:
            if i % j != 0:
                minimum = False
                break

        if minimum:
            return i
最小公倍数であるため、与えられた配列の最大値はまず最小公倍数の最小値であるため、配列の最後のインデックスから数字を1つずつ増やし、配列のインデックスの中の数字と区別することを繰り返す.結果はパスしました...放してもおかしくて、また取り戻して放した.

ユークリッドアークほう


まず,ユークリッドアーク除去法を用いて最大公約数を求めた.
def gcd(a, b):
    while b != 0:
        tmp = a % b
        a, b = b, tmp
    return a
与えられた2つの数(a,b)にa%bを加え、bが0になるまで、aにbを加えてtmpを加え、結果(a)は最大公約数となる.

最小公倍数


次に、学生時代に学んだように、与えられた2つの数(a,b)があれば、a*b=最大公倍数*最小公倍数を求める.
すなわち、最小公倍数=a*b/最大公倍数である.
それを利用してコードを書く
def gcd(a, b):
    while b != 0:
        tmp = a % b
        a, b = b, tmp
    return a


def solution(arr):
    lcm = arr[0]
    for i in arr:
        lcm = lcm * i / gcd(lcm, i)
    return int(lcm)
いいですよ.プログラマーはこの問題を見ると、1級から解き、2級からブログの記録を残したいと思っています.復習を続けることを忘れないでください.
[ジャワ]白駿1065:韓秀
[プログラマー]通学路