유클리드 호제법

코드 def gcd(a,b): # 유클리드 호제법 while b: a, b = b, a%b return a n,m = map(int, input().split()) k = gcd(n,m) print(k*'1') # 최대공약수만큼 1의 개수를 출력해주면 된다

유클리드 호제법 def gcd(a,b): while b: # b가 0이 아닐때까지 a,b = b, a%b # a는 나누는 값을 할당하고 b는 a와 b를 나누었을 때 나머지를 할당 return a # 최대공약수 int gcd(int x, int y) { while (y) { int temp = x%y; x = y; y = temp; } return x; } 유클리드 호제법은 최대공약수를 구할 때 사용하는 알고리즘이다. 증명은 어려우므로 다른 블로그를 참고하는 게 좋을 것 같다. 최소공배수는 두 수를 곱한 뒤 최대공약수로 나누면 구할 수 있다. https://roytravel.tistory.com/43 유클리드 호제법 증명 정의 유클리드 호제법이란 두 정수 사이에 최대공약수(GCD)를 보다 효과적으로 구하는..