[파이썬] 백준 2609 최대공약수, 최소공배수

백준 2609 문제 풀이

https://www.acmicpc.net/problem/2609

백준 2609 문제

풀이

최대공약수와 최소공배수는 파이썬의 math 모듈의 gcd(), lcm() 함수로 구할 수 있다.

 

최대공약수란

0이 아닌 두 정수 n과 m이 서로 공통으로 가지고 있는 약수 중 가장 큰 수를 말한다.

• 약수란
  • 어떤 수를 나누어 떨어지게 하는 수
  • 6 은 1,2,3,6 이 약수
  • 두 수를 곱해서 어떤 수를 나오면 그 두 수가 약수
• 최대 공약수 예시 : 12와 20인 경우
  • 12 : 1, 12, 2, 6, 3, 4 정렬하면 1, 2, 3, 4, 6, 12
  • 20 : 1, 20, 2, 10, 4, 5 정렬하면 1, 2, 4, 5, 10, 20
  • 같은 약수중에 제일 큰 것은 4. 최대공약수는 4

☞ 참고 사이트

최대공약수 - 위키백과, 우리 모두의 백과사전

최소 공배수란

두 정수 n 과 m의 공통 배수 중 가장 작은 수를 말한다.

• 최소 공배수 예시 12와 20인 경우
  • 12 : 12, 24, 36, 48, 60…
  • 20 : 20, 40, 60, 80…
  • 같은 배수 중에서 제일 적은 것은 60. 최소 공배수는 60

☞ 참고 사이트

최소공배수 - 위키백과, 우리 모두의 백과사전

 

풀코드

import math
var = input().split(" ")
lcmNum = 0
gcdNum = 0

gcdNum = math.gcd(int(var[0]), int(var[1])) #최대공약수
lcmNum = math.lcm(int(var[0]), int(var[1])) #최소공배수
print(gcdNum)
print(lcmNum)
"""
24 18
6
72
"""

 

☞ 파이썬 자습서 참고 사이트

https://docs.python.org/ko/3/library/math.html

math — Mathematical functions