최대공약수,최소공배수

2020-12-18 
layout: post
title:  "[파이썬] 최대공약수, 최소공배수 구하기"
author: "asadal"

최대공약수 / 최소공배수

T = int(input())
for i in range(T):
  a, b = map(int, input("두 숫자를 입력하세요(빈 칸으로 띄어쓰기) > ").split())
  num = a * b
  while (b != 0):
    temp = a % b
    a = b
    b = temp
  print(abs(a))

가장 간단한 방법.

최대공약수를 구하는 재귀함수를 정의한다.

def gcd(a, b):
  if a == 0:
    return b
  return gcd(b%a, a) # a=b%a로, b=a로.
t = int(input())
for i in range(t):
  a, b = map(int, input().split())
  res = gcd(a, b)
  print(abs(res))

최대공약수와 최소공배수 구하기

divisors = [] # 공약수를 리스트로
a, b = map(int, input("두 숫자를 입력하세요(빈 칸으로 띄어쓰기) > ").split())
for n in range(1, max(a, b)+1): # 1부터 두 숫자 중 큰 숫자까지 차례로 n값에 대입
  if a % n == 0 and b % n == 0:
    divisors.append(n) # 공약수를 divisors 리스트에 추가
gcd = max(divisors) # 최대공약수
lcm = int(a * b / gcd) # 최소공배수. 두 수의 곱을 최대공약수로 나눈 값
print(gcd, lcm)

다른 방법

from math import gcd
t = int(input())
for _ in range(t):
    a, b = map(int, input().split())
    print(a * b // gcd(a, b), gcd(a, b))
    # 최소공배수 : 두 수를 곱한 값을 두 수의 최대공약수로 나눈 값