[백준/파이썬] 2609. 최대 공약수와 최소 공배수

jwKim·2023년 1월 17일
0

💻코테코테

목록 보기
25/42

< 과제 >

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

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

[ 예제 입력 1 ]
24 18

[ 예제 출력 1 ]
6
72

< 내 코드 >

num_1, num_2 = map(int, input().split(' '))

# 각 수의 약수를 각각 따로 저장
aliquot_1, aliquot_2 = [], []

for i in range(1, num_1+1):
    if num_1 % i == 0:
        aliquot_1.append(i)

for i in range(1, num_2+1):
    if num_2 % i == 0:
        aliquot_2.append(i)
        
# 최대공약수 초기화
max_aliquot = 0

for i in range(len(aliquot_1)):
    for j in range(len(aliquot_2)):
        if aliquot_1[i] == aliquot_2[j]:
            max_aliquot = aliquot_1[i] # 순서대로 값이 덮어씌워질 것이므로 가장 공약수가 저장됨
            
print(max_aliquot)
print(int(num_1 * num_2 / max_aliquot))
  • 1부터 입력받은 수까지 반복문을 돌며 나머지를 확인한다. 나머지가 0이면, 각각의 약수 리스트에 저장한다.
  • 최대 공약수는 중첩 for문으로 구현했다. 첫 번째 수의 약수와 두 번째 수의 약수가 같은지 확인한다. 가장 마지막 수가 max_aliquot에 저장될 것이므로 최대 공약수를 찾을 수 있따.
  • 최소 공배수는 두 수의 곱을 최대 공약수로 나누면 나온다.

< 출처 >

0개의 댓글