Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- 알고리즘
- 정렬
- 공부
- Operating System
- web
- Java
- 분할메모리할당
- 파이썬
- js to ts
- 스프링
- codeup
- 타입스크립트
- 일상
- 토이프로젝트
- 기초100제
- memory
- 프로그래머스
- error
- OS
- 자료구조
- 협업
- react
- Spring
- react-redux
- 리덕스장바구니
- 코드업
- 백준
- CPU 스케줄링
- Redux
- C++
Archives
- Today
- Total
감자튀김 공장🍟
[Python] 유클리드 호제법으로 최대 공약수, 최소 공배수 구하기 본문
반응형
사실 파이썬을 사용하면 유클리드 호제법 없이 math 라이브러리를 사용하여 빠르게 최대공약수와 최소공배수를 구할 수 있다.
✅ math 라이브러리 사용
import math
a, b = map(int, input().split())
print(math.gcm(a, b)) # 최대공약수 출력
print(math.lcm(a,b)) # 최소공배수 출력
✅ 용어 정리
✔ GCD (Greate Common Divisor) - 최대 공약수
4의 약수: 1, 2, 4
24의 약수: 1, 2, 3, 4, 6, 8, 12, 24
4와 12의 공약수: 1, 2, 4 (공약수 중에서 가장 큰 수)
최대 공약수: 4
✔ LCM (Largest Common Multiple) - 최소 공배수
3의 배수: 3, 6, 9, 12, 15, 18, 21, 24, 27, 30
5의 배수: 5, 10, 15, 20, 25, 30, 35, 40, 45
3과 5의 공배수: 15, 30, 45 (공배수 중에서 가장 작은 수)
최소 공배수: 15
✅ 유클리드 호제법
✔ 2개의 자연수 a,b에 대해서 a를 b로 나눈 나머지를 r이라 하면 (단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
a와 b의 최대 공약수 == b와 r의 최대공약수
GDC(a, b) = GCD(b, r) 과 같고 r이 0이면 그때의 m이 최대공약수이다.
✔ 이 성질에 따라 b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
✅ 코드
def gcd(a, b):
while b > 0:
a, b = b, a % b
return a
def lcm(a, b):
return a * b // gcd(a, b)
✅ 참고 자료
https://donggyu.tistory.com/128
https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95
반응형
Comments