[알고리즘] 백준 1934 최소공배수 - B1

문제

링크

2024.08.23 풀이

import sys
input=sys.stdin.readline

t=int(input())
for _ in range(t):
    a,b=map(int, input().split())
    x,y=a,b
    j=0
    k=1
    for i in range(2, min(a,b)+1):
        while True:
            if a%i==0 and b%i==0:
                k*=i
                a//=i
                b//=i
            else:
                break

    print(k*(x//k)*(y//k))

다른 풀이

1. gcd 함수(-> 최대공약수)

import math

gcd = math.gcd(a,b)

2. 반복문(-> 최대공약수)

if a>b:
	a, b =b,a
    
for i in range(a, 0, -1):
	if a%i==0 and b%i==0:
    	break
gcd = i

3. 유클리드의 호제법

aa, bb = a, b
while a%b!=0:  #결과적으로 b에 최대공약수
	a,b=b,a%b
print(aa*bb//b)

check point

• 유클리드의 호제법

  2개의 자연수 a, b에 대하여(a>b), r=a%b 라 할때, a,b의 최대공약수는 b와 r의 최대공약수와 같다.

나머지가 0이 될 때까지 과정을 반복하여, 나누는 수가 a와 b의 최대공약수이다.

while a%b!=0:
	a,b=b,a%b

---

• ref