최대공약수
➡️유클리드 호제: 2 개의 자연수 a, b(a > b)에 대해서 a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다
두 수를 입력으로 받고 작은 수가 0이 될때 까지 나누기
def gcd(a, b):
while (b != 0):
r = a % b
a = b
b = r
return a
최소공배수
두 수 a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수를 나눈 것과 같다.
def lcm(a, b):
return (a * b) / gcd(a, b)
def gcd(a, b):
while (b != 0):
r = a % b
a = b
b = r
return a
'Computer Science > 알고리즘' 카테고리의 다른 글
[코드트리 챌린지] 함수활용 (1) | 2023.10.16 |
---|---|
[코드트리 챌린지] 릴레이 문제 복습 (0) | 2023.10.12 |
[코드트리 챌린지] 완전탐색 (0) | 2023.09.30 |
[코드트리 챌린지] 객체 정렬, 시뮬레이션(배열-리스트, dx-dy technique) (0) | 2023.09.27 |
[코드트리 챌린지] 정렬 (0) | 2023.09.08 |