[プログラマLv 1]最大公倍数と最小公倍数


最大公倍数と最小公倍数


質問リンク

-答えは?

def solution(n, m):
    answer = []
    for i in range(min(n, m), 0, -1):
        if n % i == 0 and m % i == 0:
            print(i)
            break
    for j in range(max(n, m), (n * m) + 1):
        if j % n == 0 and j % m == 0:
            print(j)
            break
    answer = [i, j]
    return answer
  • 最大公約数:自然数n,mで小数から1までの範囲でfor反復文を行い、自然数n,mをiで割った場合、残数が0の場合のi値が最大公約数となる.
  • 最小公倍数:自然数n,mのうちn*mまでの値範囲を有するforを繰り返し演算し、自然数n,mをそれぞれjで割った場合、残りが0の場合のj値は最小公倍数とする.
  • i(最大公約数)、j(最小公倍数)値を答え変数に割り当てて返します!
  • -答えは?

    def gcdlcm(a, b):
        c, d = max(a, b), min(a, b)
        t = 1
        while t > 0:
            t = c % d
            c, d = d, t
        answer = [c, int(a*b/c)]
    
        return answer
    これは
  • ユークリッド号除算で説明されたコードです.max,min関数を用いて変数を再割り当てするとともに,反復文を用いてユークリッドアーク除算を比較的簡単に表現していることがわかる.ユークリッド湖製法の簡単な説明は以下の通りである.
  • ユークリッドアークほう


  • ユークリッド反発法またはユークリッドアルゴリズムは、2つの自然数または正式な最大承諾数を求めるアルゴリズムの1つである.相互除算法とは、2つの数が相互除算によって最終的に所望の数を得るアルゴリズムである.
    (出典:ウィキペディア)

  • コードを書くために、もっと簡単に説明します.
    その核心原理は、自然数aをbの残数とbの最大公約数で割ったものがa,bの最大公約数に等しいことである.したがって,除算を繰り返すだけで最大公約値を求めることができる.

  • 自然数a,bが与えられた場合、aをbで割って残数を求める.次に、bをa位置に割り当て、a%b(aをbの残りの値で割った)をb位置に割り当て、b値を0に繰り返す.
    これをコードとして次のように書きます.
  • def GCD(a, b):
        while b > 0:
            a, b = b, a % b
        return a