[파이썬] 최대공약수 / 최소공배수

최대공약수

최대공약수(gcd, greatest common divisor)란?

0이 아닌 두 개 이상의 정수의 공통되는 약수 중에서 가장 큰 수이다.

따라서 두 정수 a와 b의 최대공약수는 a의 약수인 동시에 b의 약수인 수, 즉 두 정수 a, b의 공약수 중에서 가장 큰 수를 의미한다.

 

약수와 최대공약수

두 정수 a = 12와 b = 30의 최대공약수를 구해보자.

12의 약수는 1, 2, 3, 4, 6, 12 이고,

30의 약수는 1, 2, 3, 5, 6, 10, 15, 30 이다.

따라서 12와 30의 공약수는 1, 2, 3, 6 이고, 공약수 중 가장 큰 수는 6이므로

두 수 12와 30의 최대공약수는 gcd(12, 30) = 6 이다.

 

파이썬에는 math 라이브러리에 최대공약수를 반환해주는 gcd() 함수가 존재한다.

 

코드

import math gcd = math.gcd(21, 14) print(gcd)

 

실행 결과

7

 

 

최소공배수

최소공배수(lcm, Least Common Multiple)란?

0이 아닌 두 개 이상의 정수의 양의 공배수 중에서 가장 작은 수이다.

따라서 두 정수 a와 b의 최소공배수는 a의 배수인 동시에 b의 배수인 수, 즉 두 정수 a, b의 공배수 중에서 양수인 것 중 가장 작은 수를 의미한다.

 

배수와 최소공배수

두 정수 a = 2와 b = 3의 최소공배수를 구해보자.

2의 양의 배수는 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, ... 이고,

3의 양의 배수는 3, 6, 9, 12, 15, 18, 21, 24, 27, ... 이다.

따라서 2와 3의 공배수는 6, 12, 18, 24, ... 이고, 공배수 중 가장 작은 수는 6이므로

두 수 2와 3의 최소공배수는 lcm(2, 3) = 6이다.

 

 

최소공배수 구하는 방법

1. 각 수를 소인수 분해한다.

2. 공통인 소인수 중에서 거듭제곱의 지수가 같으면 그대로, 다르면 큰 것을 선택하고, 나머지 공통이 아닌 소인수까지 선택하여 모두 곱한다.

 

두 수 12와 30의 최소공배수를 소인수분해를 이용하여 구해보자.

12 = 2 x 2 x 3 = 2^2 x 3 30 = 2 x 3 x 5

 

공통인 소인수는 2와 3이다.

2의 거듭제곱의 지수는 다르기 때문에 더 큰 2^2를 선택한다.

3의 거듭제곱의 지수는 같기 때문에 그대로 3을 선택한다.

나머지 공통이 아닌 소인수 5를 선택하여 모두 곱한다.

최소공배수는 lcm(12, 30) = 2^2 x 3 x 5 = 60 이다.

 

 

최대공약수를 이용하여 최소공배수 구하기

최소공배수 = 숫자 x 숫자 / 최대공약수 lcm(a, b) = a x b / gcd(a, b)

예)

a = 12 b = 30 gcd(a, b) = 6 lcm(a, b) = a x b / gcd(a, b) = 12 x 30 / 6 = 360 / 6 = 60

 

코드

import math gcd = math.gcd(21, 14) print(x * y // gcd)

 

실행 결과

42