[BOJ] 2609번 최대공약수와 최소공배수

나르·2021년 9월 20일
0

알고리즘

목록 보기
15/15

백준#2609 최대공약수와 최소공배수 (https://www.acmicpc.net/problem/2609)

코드 - Python

유클리드의 호제법이나 Math 모듈을 사용하면 간단하게 풀 수 있다.

n,m = map(int, input().split())

# with math module
print(math.gcd(n,m), math.lcm(n,m))

# with Euclidean algorithm
def euclidean_gcd(n,m):
    while m: n,m=m,n%m
    return n
def euclidean_lcm(n,m):
    return (n*m)//euclidean_gcd(n,m)
    
print(euclidean_gcd(n,m),euclidean_lcm(n,m))

하지만 내게 최대공약수와 최소공배수는 기초수학에서 끝났기때문에 아는 것만 토대로 구현해보고싶어서...한번 작성해봤다.
m=n 혹은 n의 배수일 경우 나 중복되는 케이스 제외 등 생각보다 처리해야 할 것들이 많다ㅜㅜ

import math
def solution(n,m):
    gcd=lcm=1
    n,m=min(n,m),max(n,m)
    if m%n==0: return [n,m] # m=n 혹은 n의 배수일 경우
    for i in range(2, n + 1):
        if is_prime_number(i):
            while True:
                if n % i == 0 and m % i == 0:
                    gcd *= i
                    n, m = n // i, m // i
                else: break
    lcm=gcd*n*m
    return [gcd,lcm]
    
def is_prime_number(x):
    for i in range(2, int(math.sqrt(x))+1):
        if x % i == 0:
            return False
    return True
    
n,m = map(int, input().split())
print(solution(n,m)[0],solution(n,m)[1])
profile
💻 + ☕ = </>

0개의 댓글