20210615#(42) 백준 2609 유클리드 호제법

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

 

이 문제는 두 수가 주어졌을때 최대공약수와 최소공배수를 구하는 문제이다.

 

#1 반복문으로 풀기

gcd=1

a,b=map(int,input().split())

i=2

while(i<=min(a,b)):

    if a%i ==0 and b%i ==0:

        gcd=i

    i+=1

print(gcd)

 

#2 유클리드 호제법(최대공약수 구하기)

1)

def gcd(m,n):

    if m<n:

        m,n=n,m

if n==0:

    return m

if m%n==0:

    return n

else:

    return gcd(n,m%n)

2)

def gcd(m,n):

    while n!=0:

        t=m%n

        (m,n)=(n,t)

    return abs(m)

 

#3 유클리드 호제법 이용해 2609번 풀이

a,b=map(int,input().split())

def gcd(a,b): #최대공약수

    if b==0:

        return a

    else  return gcd(b,a%b)

 

def lcm(a,b) #최소공배수

n=gcd(a,b)

return int(n*(a/n)*(b/n)) #(==a*(b/n))

 

print(gcd(a,b))

print(lcm(a,b))