https://www.acmicpc.net/problem/2609
2609번: 최대공약수와 최소공배수
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
www.acmicpc.net
나의 코드
import sys
n, m = map(int, sys.stdin.readline().split())
num = n if n > m else m
m_yak = []
for i in range(1,num):
if (n % i == 0) and (m % i == 0):
m_yak.append(i)
print(max(m_yak))
a = 1
while a:
if (n*a) % m == 0:
print(n*a)
break
a += 1
틀렸다고 떠서 무엇인가 보니....
n과 m 둘중에 최소공약수가 나올수있기 때문에 range(1, num+1)로 수정!
import sys
n, m = map(int, sys.stdin.readline().split())
num = m if n > m else n # min(n, m)
m_yak = []
for i in range(1,num+1):
if (n % i == 0) and (m % i == 0):
m_yak.append(i)
print(max(m_yak))
a = 1
while a:
if (n*a) % m == 0:
print(n*a)
break
a += 1
다른 분들의 코드를 보니 유클리드 호제법이라고 따로 공식이 있다한다...
a를 b로 나누고 나눈수를 다시 나머지로 나누다 나머지가 0이 나올때까지 반복하는 식
a % b = c
b % c = d
c % d = 0 --> d가 최대공약수
while b != 0 :
a = a % b
a, b = b, a
print(a)
def gcd(m, n):
if n == 0:
return m
return gcd(n, m%n)
print(gcd(m, n))
print(m*n//gcd(m, n))
그런데 이미 math 모듈에 최대공약수, 최소공배수 구하는 함수가 내장되어 있다고....
import math
import sys
n, m = map(int, sys.stdin.readline().split())
print(math.gcd(n, m))
print(math.lcm(n, m))
'공부 > 알고리즘' 카테고리의 다른 글
[알고리즘][백준] 1929번 소수 구하기 - 파이썬(python) 풀이 (1) | 2024.02.28 |
---|---|
[알고리즘][백준] 1934번 최소공배수 - 파이썬(python) 풀이 (1) | 2024.02.28 |
[알고리즘][백준] 11656번 접미사 배열 - 파이썬(python) 풀이 (0) | 2024.02.27 |
[알고리즘][백준] 10824번 네 수 - 파이썬(python) 풀이 (0) | 2024.02.27 |
[알고리즘][백준] 11655번 ROT13 - 파이썬(python) 풀이 (0) | 2024.02.27 |