[알고리즘] 프로그래머스 - 최대공약수와 최소공배수

최대공약수와 최소공배수

프로그래머스

 

1. 구해야 하는 것
    # 최대 공약수와 최소 공배수
2. 1을 구하기 위해 필요한 것
    # n, m의 공약수와 공배수들
        
3. 그 외 고려사항
    # n이 m의 약수 또는 m이 n의 약수일때, 즉시 n,m을 반환
    # n과 m 이 모두 소수면 공약수는 n*m
    # 그 외에는 n*m을 최대 공약수로 나눠주면? 최소공배수 
    # 유클리드 호제법?

 

 

최대 공약수 구하기

 n과 m중 더 큰 수부터 1까지 1씩 줄여가면서 

 n과 m 둘다 나눠지는 수가 나오면

 answer 리스트에 append하고 for문 종료

 

최소 공배수 구하기

 n과 m의 곱을 최대 공약수로 나눠줌

def solution(n, m):
    answer = []
    for i in range(n if n > m else m, 0, -1):
        if n % i == 0 and m % i == 0:
            answer.append(i)
            break
    answer.append(n*m//answer[0])
    return answer