백준#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])