최대공약수란?(GCD)

• 공약수(common divisor)란 두 수 이상의 공통된 여러개의 약수를 의미한다.
• 최대공약수(GCD)란 두 수 이상의 공통된 여러개의 공약수 중 최대인 수를 가리킨다.

1. 대표적인 방법

def gcd(a, b):
    for i in range(min(a, b), 0, -1):
        if a % i == 0 and b % i == 0:
            return i

• min(a, b)로 a와 b를 나누면서 공통적으로 나머지가 0이 되는 약수가 있는지 확인하는 방법이다
  
  

2. 파이썬 math 라이브러리 방법

import math
a, b = 5, 10
math.gcd(a, b)  # 5

• 파이썬 3.9버전부터는 math 라이브러리를 사용하여 gcd를 바로 구할 수 있다.
  
  

---

baekjoon 1850_최대공약수

이 글을 쓴 큰 이유가 이 문제 때문인데
위의 2개의 방법을 써도 되지만 하나하나 수를 비교하는 것이기 때문에 시간초과가 발생한다.
유클리드 호제법을 사용한다면 효율적으로 문제를 해결할 수 있다.

유클리드 호제법?

• 두 자연수 a, b에 대하여 a를 b로 나눈 나머지 r에 대해서 a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
  이와 같은 과정을 반복하여 b가 0이 될 때 a값이 최대공약수가 된다.

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

백준 1850번 정답

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

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

print('1' * gcd(a, b))