m1ndy5's coding blog

유클리드 호제법으로 최대공약수, 최소공배수 구하기 본문

알고리즘 with python/알고리즘 스터디

유클리드 호제법으로 최대공약수, 최소공배수 구하기

정민됴 2023. 12. 6. 10:56

최대공약수 : a와 b가 있을 때 (a>b) a와 b의 최대공약수는 b와 a%b의 최대공약수와 같다.
따라서 a와 b에 계속해서 b와 a%b를 대입하고 a%b가 결국 0이 되면 그 때의 a가 최대공약수가 된다.

A, B = a, b
while B > 0:
    A, B = B, A%B
최대공약수 = A

최소공배수 : a*b를 a와 b의 최대 공약수로 나눈 것

A, B = a, b
while B > 0:
    A, B = B, A%B
최대공약수 = A
최대공배수 = a*b//A

'알고리즘 with python > 알고리즘 스터디' 카테고리의 다른 글

프로그래머스 리코쳇 로봇 with python  (1) 2023.12.12
프로그래머스 수식 최대화 with Python  (1) 2023.12.12
프로그래머스 이중우선순위큐 python  (1) 2023.12.04
Permutation & Combination 식  (0) 2023.03.16
알고리즘 스터디 2, 3일차 정리(permutation, backtracking)  (0) 2023.03.01
'알고리즘 with python/알고리즘 스터디' Related Articles more