[백준 2609 파이썬/python] 최대공약수와 최소공배수

최대공약수와 최소공배수

문제

입력

출력

예제 입력 1

예제 출력 1

풀이

1)

2)

최대공약수와 최소공배수

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	90390	52198	42350	58.092%

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

예제 입력 1

24 18

예제 출력 1

6
72

풀이

1)

def gcd(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a


def lcm(a, b):
    ans = a * b // gcd(a, b)
    return ans


a, b = map(int, input().split())

print(gcd(a, b))
print(lcm(a, b))

• 풀이과정
  1. 최대공약수를 구하는 함수 gcd(a, b): 이 함수는 유클리드 알고리즘을 사용하여 두 정수의 최대공약수를 계산합니다. b가 0이 아닐 때까지 다음과 같은 과정을 반복합니다:
     • a와 b를 나눈 나머지를 r에 저장합니다.
     • b의 값을 a에 할당합니다.
     • r의 값을 b에 할당합니다. b가 0이 되면, 최대공약수는 a에 저장되어 있습니다.
  2. 최소공배수를 구하는 함수 lcm(a, b): 이 함수는 두 정수 a와 b의 최소공배수를 계산합니다. 최소공배수는 a와 b를 곱한 값에 최대공약수로 나눈 값입니다. 즉, a * b // gcd(a, b)를 반환합니다.
  3. 사용자로부터 입력 받는 부분: 두 정수 a와 b를 입력 받아 a, b = map(int, input().split())를 사용하여 정수로 변환합니다.
  4. 결과 출력 부분: 입력 받은 두 정수 a와 b에 대해 최대공약수와 최소공배수를 계산한 후, 결과를 출력합니다.

     print(gcd(a, b))
     print(lcm(a, b))

2)

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x%y)
a,b = map(int, input().split())
g = gcd(a, b)
print(g)
print(a*b//g)

• 풀이과정
  1. 최대공약수를 구하는 함수 gcd(x, y): 이 함수는 재귀를 사용하여 두 정수의 최대공약수를 계산합니다. y가 0일 경우, 최대공약수는 x입니다. 그렇지 않으면, 함수는 y와 x를 y로 나눈 나머지로 다시 호출됩니다. 이 과정이 반복되면서 y가 0이 되면, 최대공약수가 반환됩니다.
  2. 사용자로부터 입력 받는 부분: 두 정수 a와 b를 입력 받아 a, b = map(int, input().split())를 사용하여 정수로 변환합니다.
  3. 최대공약수 계산 및 출력 부분: 입력 받은 두 정수 a와 b에 대해 최대공약수를 계산한 후, 변수 g에 저장하고 출력합니다.

     g = gcd(a, b)
     print(g)

  4. 최소공배수 계산 및 출력 부분: 최대공약수 g를 사용하여 두 정수 a와 b의 최소공배수를 계산하고 출력합니다. 최소공배수는 a와 b를 곱한 값에 최대공약수로 나눈 값입니다. 즉, a * b // g를 출력합니다.

     print(a * b // g)

Uploaded by N2T