유클리드 호제법 - 구름LEVEL
유클리드 호제법
Quiz Info
Quiz Info
유클리드 호제법
100points
Participant
307
Solved Rate
93.4%
18
11

유클리드 호제법은 a, b, q, r 이 정수라고 가정할 때

        a = b * q + r  =>  gcd(a,b) = gcd(b,r)

a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 원리를 이용하여 최대공약수를 구합니다. 

gcd(a, b)에서 만약 b가 0이 되면 a가 처음에 주어진 수의 최대공약수가 됩니다.

예를 들어 108 과 80 의 최대공약수를 구한다면

gcd(108, 80) = gcd(80, 28) = gcd(28, 24) = gcd(24, 4) = gcd(4, 0)

이므로 최대공약수는 4가 됩니다.

두 수를 입력하였을 때 유클리드 호제법을 이용하여 최대 공약수를 출력하는 프로그램을 작성하십시오.


입력

두 양의 정수

출력

두 양의 정수의 최대 공약수


Input/Output Example
:
Blank
:
Line Break
:
Tab
Example 1
Input
1218
Output
6
Example 2
Input
68
Output
2
⋇ Please keep the input and output formats carefully
Quiz Info
Q & A
Q&A forum that anyone can ask and answer.
Share your questions and answers with other students and grow together!

Registered Questions(0)