[プログラマ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
-答えは?
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
これはユークリッドアークほう
ユークリッド反発法またはユークリッドアルゴリズムは、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
Reference
この問題について([プログラマLv 1]最大公倍数と最小公倍数), 我々は、より多くの情報をここで見つけました https://velog.io/@lck0827/프로그래머스Lv1-최대공약수와-최소공배수テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol