Öklid Algoritması Nedir?
Öklid algoritması, bilinen en eski algoritmalardan biridir ve yaklaşık MÖ 300 yılında Yunan matematikçi Öklid tarafından tanımlanmıştır. İki tam sayının en büyük ortak bölenini (OBEB) bulur; yani her ikisini de kalansız bölen en büyük sayıyı. Bu hesaplama aracı, algoritmayı herhangi iki negatif olmayan tam sayıya uygular ve aynı zamanda bu sayıların en küçük ortak katını (OKEK) da verir.
Nasıl Kullanılır?
İki sayınızı a ve b olarak işaretlenmiş alanlara girin ve hesaplayın. Araç, ana sonuç olarak OBEB değerini, ikincil sonuç olarak da OKEK değerini gösterir. Sayıların sırası önemli değildir — obeb(48, 36), obeb(36, 48) ile aynıdır. Negatif girişler mutlak değerleriyle işlenir; sayılardan biri 0 ise OBEB doğrudan diğer sayıya eşittir.
Formülün Açıklaması
Algoritma basit bir mantığa dayanır: a ve b sayılarının her ortak böleni, aynı zamanda bu sayıların kalanı olan a mod b değerini de böler. Bu nedenle büyük sayıyı sürekli kalanla değiştiririz:
$$\gcd(a,b) = \gcd(b,\, a \bmod b)$$
temel durum ise $$\gcd(a,0) = a$$ şeklindedir.
Her adım sayıları hızla küçülttüğü için, çok büyük değerler bile yalnızca birkaç tekrarla çözülür. OKEK ise $$\operatorname{lcm}(a,b) = \frac{a \times b}{\gcd(a,b)}$$ formülüyle hesaplanır.
Örnek Çözüm
obeb(48, 36) değerini bulalım:
\(48 \bmod 36 = 12\) → obeb(36, 12)
\(36 \bmod 12 = 0\) → \(\gcd(12, 0) = \mathbf{12}\).
Yani OBEB 12'dir ve $$\operatorname{lcm} = \frac{48 \times 36}{12} = \frac{1728}{12} = \mathbf{144}$$ olur.
Sıkça Sorulan Sorular
Her iki sayı da 0 ise ne olur? Burada 0 ile 0'ın OBEB değeri 0 olarak tanımlanır; pozitif bir ortak kat bulunmadığı için OKEK de 0'dır.
Neden bölenleri tek tek listelemekten daha hızlıdır? Algoritma, her böleni bulmak yerine kalan kısayolunu kullanır ve böylece her adımda problemin boyutunu ciddi şekilde küçültür — genellikle logaritmik sürede çalışır.
Çok büyük sayılarla çalışabilir mi? Evet. Öklid algoritması, çok basamaklı sayılarda bile yalnızca az sayıda mod işlemi gerektirdiği için son derece verimlidir.
