[98일차] 최대공약수와 최소공배수 - 백준 - 2609(python - 정수론, 유클리드 호제)

문제 설명

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

 

입력

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

 

출력

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

 

예제 입출력

24 18

6 72

 

코드 및 설명

n, m = map(int, input().split(" "))
count = 2
share = []
remain = 0
answer = 1

while True:  
  if n < count or m < count:
    for val in share:
      answer *= val      
      
    remain = answer * n * m
    break 
    
  if n % count == 0 and m % count == 0:    
    share.append(count)
    n = n // count
    m = m // count
  else:
    count += 1  
    
print(answer)
print(remain)

 

이 문제는 최대 공약수 최소 공배수를 구하는 문제이다. 유클리드 호제법을 활용하면 아주 간단한게 풀 수 있다.

 

위에 코드는 유클리드 호제법을 이용하지 않고 풀어본 것이다.

 

최대 공약수는

 

 2 ) 24 18

 3 ) 12  9

       4   3

 

나눈 값을 곱해주면 그게 최대 공약수 2 x 3 = 6

나눈 값 + 나머지 값 전부 곱해주면 최소 공배수  2 x 3 x 4 x 3 = 72

 

이걸 코드로 풀어서 작성한 것이다.

 

while돌리는 데 count = 2부터 시작 n % count == 0 and m % count == 0  해당 카운트의 값으로 두 숫자의 나머지가 0이 

 

나와야 해당 카운트의 값으로 나눠진 거기 때문에 나눈 몫이므로 share 저장해준다. 그 다음 n, m 나눈 몫을 저장.

 

반복하다가 안 나눠지는 수가 나오면 count + 1하면서 계속 반복

 

n, m보다 count가 큰 게 하나라도 나오면 break한다.

 

share 값 전부를 곱해서 answer 저장하고, remail에 answer * n * m을 해주면

 

최대공약수, 최소 공배수를 구할 수 있게 된다.

 

n, m = map(int, input().split(" "))
remain = (n*m)
while m != 0:
  [n, m] = [ m, n%m ]
  
print(n)
print(int(remain / n))

 

위에 코드가 유클리드 호제법으로 푼 것이다. 그냥 푼 코드보다 훨씬 짧은 걸 볼 수 있다. 해당 알고리즘은 외워야겠다.