공약수, 최대공약수(파이썬 출력)

 

 

공약수와 최대공약수

 

---

 

 

 

공약수

두 개 이상의 수에서 공통된 약수를 공약수라고 한다

 

 

최대공약수

공약수 중 가장 큰 수를 최대공약수라고 한다.

소인수분해를 이용하면 최대공약수 및 공약수를 구할 수 있다.

좀 더 편리하게 최대공약수 구하는 방법 : 소수로 나눗셈

 

 

수 두개의 공약수 구하기

num1 = int(input('1보다 큰 정수 입력: '))
num2 = int(input('1보다 큰 정수 입력: '))

for i in range(1, (num1 + 1)): #1부터 출발해서 num+1까지 반복합니다.
    if num1 % i == 0 and num2 % i == 0: #공통된 약수이기에 num1, nm2 같이 진행
        print('공약수: {}'.format(i))

 

 

수 두개의 최대 공약수 구하기

num1 = int(input('1보다 큰 정수 입력: '))
num2 = int(input('1보다 큰 정수 입력: '))
maxNum = 0

for i in range(1, (num1 + 1)):
    if num1 % i == 0 and num2 % i == 0:
        print('공약수: {}'.format(i))
        maxNum = i #공약수가 나올때마다 maxNum에다 할당을 해준다.

print('최대공약수: {}'.format(maxNum))

 

 

수 세개의 공약수 구하기

num1 = int(input('1보다 큰 정수 입력: '))
num2 = int(input('1보다 큰 정수 입력: '))
num3 = int(input('1보다 큰 정수 입력: '))

for i in range(1, (num1 + 1)):
    if num1 % i == 0 and num2 % i == 0 and num3 % i == 0:
        print('공약수: {}'.format(i))

 

 

유클리드 호제법을 이용해서 최대공약수를 구할 수 있다.

 → x,y의 최대공약수는 y,r(x%y)의 최대공약수와 같다.

num1 = int(input('1보다 큰 정수 입력: '))
num2 = int(input('1보다 큰 정수 입력: '))

temp1 = num1; temp2 = num2 #받은 숫자 두개를 저장을 해둔다.

while temp2 > 0: #temp2가 0보다 클때만 계속돈다.
    temp = temp2 #temp2를 tmep에다 임시로 저장한다.
    temp2 = temp1 % temp2
    temp1 = temp

print('{}, {}의 최대공약수: {}'.format(num1, num2, temp1))

for n in range(1, (temp1 + 1)):
    if temp1 % n == 0:
        print('{}, {}의 공약수: {}'.format(num1, num2, n))