[기초 수학] 최대공약수 최소공배수 with python

공약수

두 대 이상의 수에서 공통된 약수
(최대공약수의 약수들과 같다)

최대공약수

공약수 중 가장 큰 수
공통인 소인수의 거듭제곱에서 지수가 작은 수를 모두 곱한다.

#for문 이용해서 최대공약수 구하기 (조건 : Num1<Num2)
num1 = int(input("0보다 큰 정수 입력1 : "))
num2 = int(input("0보다 큰 정수 입력2 : "))
maxNum = 0

for i in range(1, num1+1):
    if num1 % i == 0 and num2 % i == 0:
        print(f"공약수: {i}")
        maxNum = i
print(f"최대공약수: {maxNum}")

유클리드 호제법

x, y의 최대공약수는 y와 r의 최대 공약수와 같다. (r = x%y의 나머지)

# 유클리드 호제법 이용해서 최대공약수 구하기

temp1 = num1; temp2 = num2
while temp2>0: # temp1 % temp2 = r
    temp = temp2
    temp2 = temp1%temp2
    temp1 = temp # 최대 공약수

print(f"최대공약수: {temp1}")

공배수

두 개 이상의 수에서 공통된 배수

최소공배수

공배수 중 가장 작은 수
공통인 소인수의 거듭제곱에서 지수가 크고 공통아닌 수를 모두 곱한다.
(두 수의 소인수 중 지수가 큰 것 듯을 모두 곱한다.)

#for문 호제법 이용해서 최대공약수 구하기
num1 = int(input("0보다 큰 정수 입력1 : "))
num2 = int(input("0보다 큰 정수 입력2 : "))
maxNum = 0

for i in range(1, num1+1):
    if num1 % i == 0 and num2 % i == 0:
        print(f"공약수: {i}")
        maxNum = i
print(f"최대공약수: {maxNum}")
numNum = (num1 * num2) // maxNum
print(f"최대공약수: {numNum}")