Öklid Algoritması ile en büyük ortak bölenin (ebob) nasıl bulunabileceğini hem iteratif, hem de rekürsif yolla anlatmaya çalıştım bu videoda.

► Öklid Algoritması: https://tr.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm

İki A ve B tam sayısının Ortak Bölenlerinin En Büyüğünün (OBEB), A ve B’yi bölen en büyük tam sayı olduğunu hatırlayalım.

Öklid Algoritması, iki tam sayının OBEB’ini hızlıca bulmak için kullanılan bir yöntemdir.

OBEB(A,B)’nin bulunması için Öklid Algoritması şu şekildedir:

► Eğer A=0 ise, OBEB(0,B)=B olacağı için OBEB(A,B)=B olur ve bu noktada durabiliriz.

► Eğer B=0 ise, OBEB(A,0)=A olacağı için OBEB(A,B)=A olur ve bu noktada durabiliriz.

► A sayısını bölüm ve kalan formunda yazın (A=B⋅Q+R)

►OBEB(A,B)=OBEB(B,R) olduğu için, OBEB(B,R)’yi Öklid Algoritmasını kullanarak bulun

► Ortak bölen nedir? https://tr.wikipedia.org/wiki/Ortak_b%C3%B6len

Matematikte, sıfır olmayan iki veya daha fazla pozitif tam sayının en büyük ortak böleni, tam sayıların hepsini de bölen en büyük pozitif tam sayıdır. Örneğin; 8 ve 12’nin ebob’u 4’tür.

En büyük ortak bölen aynı zaman da en büyük ortak faktör (ebof), en yüksek ortak faktör (eyof) ile de isimlendirilir.

        /// <summary>
        /// En büyük ortak böleni bulmak
        /// </summary>
        static int GreatestCommonDivisor(int a, int b)
        {
            while(a != 0 || b != 0)
            {
                if(a > b)
                {
                    a %= b;
                }
                else
                {
                    b %= a;
                }
            }

            return a | b;
        }

        /// <summary>
        /// En büyük ortak bölüne rekürsif yolla bulmak
        /// </summary>
        static int GcdRecursive(int a, int b)
        {
            if(b == 0)
            {
                return a;
            }
            else
            {
                return GcdRecursive(b, a % b);
            }
        }