[Python Bronze I 2609] 최대공약수와 최소공배수

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

 

시간 제한	메모리 제한
1초	128MB

 

문제

• 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

 

입력

• 첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

 

출력

• 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

 

알고리즘 분류

• 수학
• 정수론
• 유클리드 호제법

 

---

 📖 Code

num1, num2 = map(int, input().split())
num3,result1,result2 =1,1,1


if num1 > num2:
    num3 = num2
else:
    num3 = num1
    
for i in range(2,num3+1):
    if((num1%i)==0 and (num2%i)==0):
        result1 = i
        
print(result1)      
result2 = (num1/result1)*(num2/result1)*result1
print(int(result2))

 ✅ Comment

입력받은 두수 중 작은 수를 기준으로 0부터 기준이 되는 수까지 반복하여 입력받은 두수가 동시에 나누어떨어지는 경우를 구합니다. 이때 나오는 값은 최대 공약수입니다.



최소 공배수를 구하는 방법은 두수의 약수 중 최대 공약수에 해당하는 중복된 값을 제외한 모든 약수를 곱해주면 최소 공배수가 나오게 됩니다.



입력받은 값에 각각 최대 공약수 값을 나누어 주고 두 값을 곱한 뒤 마지막으로 최대 공약수를 곱해주면 최소 공배수가 나오게 됩니다.