목록2020/05/10 (1)

준호씨의 블로그

python - 최대공약수 구하기

공약수는 두 개 이상의 자연수가 공통으로 갖는 약수입니다. 예를 들어 4의 약수는 1,2,4, 6의 약수는 1,2,3,6입니다. 공약수는 1,2입니다. 최대공약수는 공약수들 중 가장 큰 수인 2입니다. 참고로 서로소란 최대공약수가 1인 두 자연수를 서로소라고 합니다. 3과 4는 최대공약수가 1입니다. 그러므로 3과 4는 서로소입니다. python에서 최대공약수를 구할 때 gcd함수를 이용할 수 있습니다. >>> from math import gcd >>> gcd(4, 6) 2 유클리드 호제법을 이용하여 gcd를 직접 구현할 수 있습니다. def gcd_my(a, b): if b == 0: return a else: return gcd_my(b, a % b) 배열의 숫자들의 최대공약수를 구하고 싶다면 다음..
개발이야기 2020. 5. 10. 23:50
Prev 1 Next