최대공약수, 최소공배수 참 오랜만에 듣는 단어들 아닌가요? 오늘은 파이썬 언어로 이들을 유클리드 호제법 알고리즘을 사용해 구해 보겠습니다.
약수 a = bc 정수 a를 0이 아닌 정수 b로 나눌 때 정수 c가 존재한다면 b를 a의 약수라 하며 a는 b의 배수가 됩니다. 모든 정수는 1 과 -1을 약수로 가집니다.
이번 시간에는 양수만 다루겠습니다. 12 양의 약수는 1 * 12 = 2 * 6 = 3 * 4 즉 {1, 2, 3, 4, 6, 12} 입니다. 그리고 30 양의 약수는 1 * 30 = 2*15 = 3 *10 = 5 * 6 즉 {1, 2, 3, 5, 6 ,10, 15, 30} 입니다.
GCD 위에서 12와 30의 공통된 약수는 {1, 2, 3, 6} 이며 이중 제일 큰 수 즉 최대공약수는 {6} 이 됩니다. 예전 수학 시간에 이런 식으로 최대공약수, 최소공배수를 구했을 같은데요.
최소공배수는 두 수를 곱한 결과에 최대공약수를 나누어 구할 수도 있어요. 즉 12 * 30 / 6...
#
유클리드호제법
#
최대공약수
#
최소공배수
#
파이썬
#
파이썬최대공약수
#
파이썬최소공배수
원문 링크 : 파이썬 최대공약수 최소공배수 유클리드 호제법
