1단계_최대공약수와 최소공배수

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.제한 사항

• 두 수는 1이상 1000000이하의 자연수입니다.

입출력 예

nmreturn

3	12	[3, 12]
2	5	[1, 10]

입출력 예 설명

입출력 예 #1
위의 설명과 같습니다.

입출력 예 #2
자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

 

풀이

def solution(a, b):
    answer = []
    
    for i in range(min(a, b), 0, -1) :
        if a % i == 0 and b % i == 0:
            answer.append(i)
            break
    
    for i in range(max(a, b), (a*b)+1) :
        if i % a == 0 and i % b == 0:
            answer.append(i)
            break
    print(answer)
    return answer

#최대 공약수 구하기 설명 :

a,b, 중 가장 작은 숫자부터 1까지 -1을 하며 for문을 실행시킵니다. 만약 a%i , b%i 값이 모두 딱 떨어져서 나머지가 없는 상태 (==0) 라면 이 때 사용된 i는 a와b의 최대 공약수입니다. (a,b를 모두 나눌 수 있는 약수 중 가장 큰 수) 

 

#최소 공배수 구하기 설명 : 

a,b 중 더 큰 숫자부터 a*b의 수까지 for문을 실행시킵니다. 더 큰 숫자부터 실행하는 이유는 a, b의 배수들 중 공통 부분을 찾는 것이기 때문에 a,b 중 작은 수부터 시작하게되면 i가 ++1이되면서 둘 중 큰수에 도달할 때까지 for문은 헛돌게 됩니다.

i%a, i%b ==0 모두 값이 떨어지는 나머지가 없는 상태라면 이 때 사용된 i는 a와b의 최소공배수입니다. 

 

https://codingpractices.tistory.com/34 참고

 

최대공약수란 ? 

GCD (Greatest Common Divisor) 

Common Divisor -> 라는 이름에서 알 수 있듯이 두 수 혹은 그 이상의 여러 수의 공통인 약수 중, 최대인 것. 

즉, 수들의 각각의 약수 중 공통이며 가장 큰 수를 최대공약수라고 한다. 

ex) 

8 의 약수 - 1,2,4,8  

10 의 약수 - 1,2,5,10  

8과 10의 공통 약수 : 1,2 중 가장 큰 수 : 2 

8과 10의 최대공약수 : 2

최소공배수란? 

LCM (Largest Common Multiple)

두 수, 혹은 그 이상의 수들의 공통인 배수 중 최소, 가장 작은 수. 즉, 수 들의 각각의 배수 중 공통이며 가장 작은 수를 최소공배수라고 한다. 

 

10의 배수 : 10,20,30,40,50,60,70,80,90,100,110,120,130,....

12의 배수 : 12,24,36,48,60,72,84, 96, 108, 120,....

10과 12의 공통 배수 : 60, 120, ... -> 공배수 중 가장 작은 것 60

10과 12의 최소공배수 : 60