백준 파이썬 2609번 최대공약수와 최소공배수

1.유클리드호제법

첫번째 방식은 유클리드 호제법으로 푼 내용이다.

일종의 공식과 같은 것이니, 네이버나 구글 찾아보면

유클리드호제법이라고 설명이 잘 나와있다.

 

i,j = map(int,input().split())
n,m = max(i,j),min(i,j)

while m>0:
    n,m = m,n%m

print(n)
print((i*j)//n)
#24,18->18,6->6,0 n=6
#24*18/6 = 72

입력받는 두 수 중 큰수와 작은 수를 먼저 n,m에 다시 저장하고

m>0조건에서 while문을 돌려서 n에는 m을 m에는 n%m(나머지수)를 저장한다.

n은 최대공약수

(i*j)//n은 최소공배수를 나타낸다.

문제에서 24,18을 입력하면

24,18->18,6->6,0 이렇게 되서 n=6

24*18/6 =72 m은 72가 된다.

 

2.for문

유클리드호제법을 몰랐다면 있는 그대로 for문을 돌려준다.

tmp라는 리스트를 하나만들고,

1부터 두 수중 작은 수까지 for문을 돌린다.

나누었을때 나누어 떨어지는 수를 tmp에 더하고 sorting해준다.

그럼 마지막 수가 가장 큰 수이다.

최대공약수는 tmp리스트의 마지막 수이고

최소공배수는 마지막수 * 마지막수를 나눈 각 몫을 곱해주면 된다.

a,b = map(int,input().split())
tmp = []

for i in range(1,min(a,b)+1):
    if a%i == 0 and b%i ==0:
        tmp.append(i)
        tmp.sort()

print(tmp[-1])
print(tmp[-1]*(a//tmp[-1])*(b//tmp[-1]))

3.파이썬 함수 활용

 

파이썬 함수에는 최대공약수,최소공배수가 있어서 그냥 그대로 함수만 써주면 끝이다.

 

import math
a, b = map(int, input().split())
print(math.gcd(a,b))
print(math.lcm(a,b))