[유클리드 알고리즘] GCD 함수 (백준 1934 최소공배수)

 GCD는 greatest common divisor의 약자로 최대공약수를 뜻한다

 

 유클리드 알고리즘은 최대공약수를 쉽게 구하는 방법으로

 "비교대상의 두 개의 자연수 a와 b에서(단 a>b) a를 b로 나눈 나머지를 r이라고 했을때 GCD(a, b) = GCD(b, r)과 같고 r 이 0이면 그때 b가 최대공약수이다."라는 원리를  활용한 알고리즘" 이다

ex) GCD(24,16) -> GCD(16,8) -> GCD(8,0) : 최대공약수 = 8

 

import sys
input=sys.stdin.readline
 
for _ in range(int(input())):
    a, b=map(int, input().split())
 
    #최소공배수
    #공통으로 나누어지는 수 중 가장 큰 수 * 나머지
    #없으면 다 곱합
    div=1
    i=1
    while i<=a and i<=b :
        if a%i==0 and b%i==0:
            div=i
        i += 1
 
    result=div*(a//div)*(b//div)
    print(result)

처음에는 i를 1씩 증가시켜 공통으로 나누는 수 중 가장 큰 수를 구하려 했는데 시간초과가 떴다

 

 

import sys
input=sys.stdin.readline
 
def GCD(a, b):
    if b==0:
        return a
    return GCD(b, a%b)
 
for _ in range(int(input())):
    a, b=map(int, input().split())
 
    div=GCD(b, a)
 
    result=div*(a//div)*(b//div)
    print(result)

GCD 알고리즘을 적용 시킨 후 성공했다

 

 

 

참고

coding-factory.tistory.com/599