오늘은 공약수, 최대공약수의 정의와
파이썬으로 두개의 수를 입력하면 공약수의 최대 공약수를 출력하는 코드를 작성하도록
하겠습니다.
공약수 : 두 개 이상의 수에서 공통된 약수를 공약수라고 합니다.
예를 들어 , 12의 약수는 1,2,3,4,6,12 이고 20의 약수는 1,2,4,5,10,20 이니 공약수는 1,2,4 가 될 것입니다.
최대공약수 : 공약수 중 가장 큰 수를 최대공약수라고 합니다.
12와 20의 공약수는 1,2,4 이니 최대공약수는 4가 될 것입니다.
*소인수분해를 이용하면 최대공약수 및 공약수를 구할 수 있습니다.
최대공약수에 공통인 소인수의 거듭제곱에서 지수가 작은 수를 모두 곱하면 될 것입니다.
12의 소인수 분해 : 2^2 X 3 이고 20의 소인수분해는 2^2 X 5 이니
12 , 20의 2^2를 가져오면 그것이 최대공약수가 (4) 될 것입니다.
최대공약수의 약수들이 공약수이니 4의 약수인 1,2,4가 12 와 20의 공약수가 되는 것이죠.
** 좀 더 편리하게 최대공약수를 구하는 방법이 있습니다. 소인수 분해를 하는 방법입니다.
이 그림을 참고하면 좋을 것입니다.
파이썬
num1 = int(input('1보다 큰 정수 입력: '))
num2 = int(input('1보다 큰 정수 입력: '))
MaxNum = 0
for i in range(1, (num1 + 1)):
if unm1 % i == 0 and num2 % i ==0:
print('공약수:{}].format(i))
maxNum = i
print('최대공약수: {}.format(maxUnm))
ex) 1보다 큰 정수 입력에 12, 36 을 넣으면
공약수는 1,2,3,4,6,12가 될 것이다.
-파이썬 int() 함수 : 입력한 실수(또는 정수)로부터 얻어진 정수 객체를 반환합니다.
-파이썬 inpit() 함수 : input은 입력되는 모든 것을 문자열로 취급한다. --> 또한, 파이썬은 input 함수를 사용하여 키보드 입력을 받는다. 출력하고 싶은 메시지는 input 함수의 인자로 전달하면 된다. input 함수의 리턴값은 문자열이다.
세 개의 수를 입력하면 공약수와 최대공약수를 출력하는 코드를 작성하자.
num1 = int(input('1보다 큰 정수 입력: '))
num2 = int(input('1보다 큰 정수 입력: '))
num3 = int(input('1보다 큰 정수 입력: '))
maxNum = 0
for i in range(1, (num1 + 1)):
if num1 % i ==0 and num2 % i ==0 and num3 % i == 0:
print('공약수: {}'.format(i)
MaxNum = i
print('최대공약수: {}' : format(maxNum))
- 그리고 또한 유클리드 호제법을 이용해서 최대공약수를 구할 수 있다.
파이썬 함수로는?
유클리드 호제법을 이용해서 최대공약수를 구할 수 있다.
num1 = int(input('1보다 큰 정수 입력: '))
num2 = int(input('1보다 큰 정수 입력: '))
tem1 = num1 ; tem2 = num2
while tem2 > 0 :
temp = temp2
temp2 = temp1 % temp2
temp1 = temp
print('{}, {}의 최대공약수 : {}'. format(num1, num2, temp1))
rof n in range(1, (tem1 +1)):
if tem1 % n == 0:
print('{}, {}의 공약수: {}'.format(num1 , num2, n))
