001_Euclid

<유클리드의 최대공약수 알고리즘>

2개의 자연수의 최대공약수 = (큰 수 - 작은수)와 (작은수)와의 최대공약수와 같다

뺄셈 대신 나눗셈을 이용하면 빠른 계산 가능

 

<Euclid 호제법 - 최대공약수>

이 알고리즘의 핵심 아이디어는 두 정수의 최대공약수를 찾을 때,

큰 수와 작은 수의 나머지를 구해서 작은 수를 계속해서 업데이트해 나가는 것

이것을 반복하면 최대공약수를 구할 수 있다

 

001_Euclid

using System.Windows;

namespace _001_Euclid
{
    /// Euclid 호제법 - 최대공약수
    public partial class MainWindow : Window
    {
        public MainWindow()
        {
            InitializeComponent();
        }

        private void button_Click(object sender, RoutedEventArgs e)
        {
            int x = int.Parse(textBox1.Text);
            int y = int.Parse(textBox2.Text);
            int gcd = Euclid(x, y);
            txtResult.Text = "GCD = " + gcd.ToString();
        }

        private int Euclid(int x, int y)
        {
            // y가 0이라면 x가 최대공약수이므로 x 리턴
            if (y == 0)     
                return x;
            // x와 y의 나머지를 새로운 x로 설정하고 y 그대로 유지
            else
                return Euclid(y, x % y);  
        }
    }
}

유클리드 알고리즘

private int Euclid(int x, int y)
{
    // y가 0이라면 x가 최대공약수이므로 x 리턴
    if (y == 0)
         return x;
    // x와 y의 나머지를 새로운 x로 설정하고 y 그대로 유지
    else
        return Euclid(y, x % y);
}