#14. Algorithm10_python) 최대공약수, 최소공배수

문제) 최대공약수, 최소공배수

두 수를 입력받아, 두 수의 최대공약수와 최소공배수를 계산하여 출력

 

---

 

step1) 테스트1 : ex) n1 = 30, n2 = 24

# 최대공약수1

n1 = 30
n2 = 24
min = 0

# 둘 중 작은 값 구하기
if n1 < n2:
    min = n1
else:
    min = n2

for i in range(min, 0, -1):          # 작은 수에서 1씩 내려가며,
    if n1 % i == 0 and n2 % i == 0:  # 공통 약수
        print(i)
        break

>>>
6

# =================================

# 최소공배수1

n1 = 30
n2 = 24
max = 0

# 둘 중 큰 값 구하기
if n1 < n2 :
    max = n2
else :
    max = n1

for i in range(max, n1 * n1 +1):      # 큰 수에서 1씩 올라가며,
    if i % n1 == 0 and i % n2 == 0:   # 공통 배수
        print(i)
        break

>>>
120

 

step2) 테스트1 : min( ), max( ) 메서드 이용

# 최대공약수2

n1 = 30
n2 = 24

for i in range(min(n1, n2), 0, -1):   # min() 메서드 이용
    if n1 % i == 0 and n2 % i == 0:
        print(i)
        break
        
>>>
6

# ==================================

# 최소공약수2

n1 = 30
n2 = 24

for i in range(max(n1, n2), (n1 * n2) + 1):   # min() 메서드 이용
    if i % n1 == 0 and i % n2 == 0:
        print(i)
        break
        
>>>
120

 

step3) 메서드

# 최대공약수

n1 = 30
n2 = 24

def GCD(n1, n2):
    for i in range(min(n1, n2), 0, -1):
        if n1 % i == 0 and n2 % i == 0:
            return i
            break

print(f'{n1}, {n2}의 최대공약수 : {GCD(n1, n2)}')

>>>
30, 24의 최대공약수 : 6

# ================================================

# 최소공배수

n1 = 30
n2 = 24

def LCM(n1, n2):
    for i in range(max(n1, n2), (n1 * n2) + 1):
        if i % n1 == 0 and i % n2 == 0:
            return i
            break

print(f'{n1}, {n2}의 최소공배수 : {LCM(n1, n2)}')

>>>
30, 24의 최소공배수 : 120

 

step4) 메서드 : 숫자 입력받아서

# 최대공약수

n1 = int(input("숫자1 입력 : "))
n2 = int(input("숫자2 입력 : "))


def GCD(n1, n2):
    for i in range(min(n1, n2), 0, -1):
        if n1 % i == 0 and n2 % i == 0:
            return i
            break

print(f'{n1}, {n2}의 최대공약수 : {GCD(n1, n2)}')

>>>
숫자1 입력 : 10
숫자2 입력 : 35
10, 35의 최대공약수 : 5

# ================================================

# 최소공배수

n1 = int(input("숫자1 입력 : "))
n2 = int(input("숫자2 입력 : "))

def LCM(n1, n2):
    for i in range(max(n1, n2), (n1 * n2) + 1):
        if i % n1 == 0 and i % n2 == 0:
            return i
            break

print(f'{n1}, {n2}의 최소공배수 : {LCM(n1, n2)}')

>>>
숫자1 입력 : 10
숫자2 입력 : 35
10, 35의 최소공배수 : 70

---

# 배운점

• for문 더 깊이 이해
• min, max 로직 구현

# 소회

• 구글링 해보니, '유클리드 호제법'이란 방식으로 알고리즘 구현 -> 추후 공부하기