목록유클리드 호제법 (1)

m1ndy5's coding blog

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

최대공약수 : 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/알고리즘 스터디 2023. 12. 6. 10:56
이전 Prev 1 Next 다음