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

1. 공약수

두 개 이상 자연수의 공통된 약수를 의미한다.

12의 약수
1, 2, 3, 4, 6, 12

15의 약수
1, 3 5, 15

공약수
1, 3

2. 최대공약수

공약수 중 가장 큰 약수를 의미한다.

각 자연수의 약수를 구해 가장 큰 공약수를 찾거나, 두 수를 공통으로 나눌 수 있는 소수로 나눈 뒤 몫 부분의 곱(a*b*c*...*n-1*n) 을 구해 최대공약수를 찾을 수 있다.

3 )  12  15

       4    5

- 12의 최대 공약수는 3이다.

 

3. 파이썬에서의 최대공약수 예제

import math

def gcd(n) :
  lst_n = set()
  for i in range(1, n+1) :
    if n % i == 0 :
      lst_n.add(i)
  return lst_n

a, b = map(int, input().split())
lst_a = gcd(a)
lst_b = gcd(b)
print(max(lst_a&lst_b)) # 1번째 방법
print(math.gcd(a, b)) # 2번째 방법 파이썬 3.5이상

a와 b 각각의 약수를 구한 뒤 중복된 값(공약수)의 최댓값을 출력하도록 작성하였다.

 

3. 공배수

두 개 이상 자연수의 공통된 배수를 의미한다.

3의 배수
3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48
4의 배수
4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52
공배수
12, 24, 36, 48 . . .

4. 최소공배수

공배수 중 가장 작은 수를 의미한다. 

각 자연수의 배수를 구해 공배수를 찾거나, 최대공약수를 구하는 것과 동일하게 두 수를 공통으로 나눌 수 있는 소수로 나눈 뒤 몫 부분과 가장 아래의 서로소 부분를 모두 곱하여 찾을 수 있다.

1 )   3    4

       3    4

- 3과 4의 최소공배수는 1 * 3 * 4 = 12 이다.

 

5. 파이썬에서의 최소공배수 예제

import math

def lcm(a, b) :
  i = 1
  while True :
    if b*i % a == 0 :
      return b*i
    else :
      i += 1

a, b = map(int, input().split())
print(lcm(a, b)) # 1번째 방법
print(math.lcm(a, b)) # 2번째 방법 파이썬 3.9이상

1 부터 최소 공배수가 나올 때 까지 i를 증가시키면서 b*i 한 값이 a의 배수인지를 확인하기 위해 나머지를 구해 0이 나오면 출력하도록 작성하였다.

 

6. 한번에 최대공약수, 최소공배수 구하기 예제(유클리드 호제법)

def gcd(a,b) :
    while b > 0 :
      temp = b
      b = a % b
      a = temp
    return a

def lcm(a, b) :
  value = gcd(a, b)
  return value, (a*b) // value
    
a, b = map(int, input().split())
print(*lcm(a,b), sep='\n')