En Büyük Ortak Bölen (EBOB) Algoritması

Matematikte sıkça karşılaşılan problemlerden biri, iki veya daha fazla sayının En Büyük Ortak Bölenini (EBOB) bulmaktır. Bu yazıda, EBOB’un ne olduğunu açıklayarak, farklı yöntemlerle EBOB hesaplama algoritmalarını inceleyeceğiz ve örneklerle detaylandıracağız.

EBOB Nedir?

En Büyük Ortak Bölen (EBOB), iki ya da daha fazla tam sayının ortak bölenleri arasında en büyük olanıdır. Örneğin, 12 ve 18 sayılarının EBOB’u 6’dır, çünkü her iki sayı da 6’ya bölünür ve 6, bu sayıları bölen en büyük sayıdır.

12’nin bölenleri: 1, 2, 3, 4, 6, 12
18’in bölenleri: 1, 2, 3, 6, 9, 18
12 ve 18’in ortak bölenleri: 1, 2, 3, 6
Bu durumda en büyük ortak bölen 6’dır.

EBOB Hesaplama Algoritmaları

EBOB’u bulmak için kullanılan birkaç farklı algoritma mevcuttur. Şimdi bu yöntemleri inceleyelim.

1. Yöntem: Bölenleri Listeleme Yöntemi

Bu yöntemde her iki sayının da bölenleri listelenir ve ortak bölenler bulunur. Ortak bölenlerin en büyüğü ise EBOB’dur. Ancak bu yöntem, büyük sayılar için pratik olmadığından, genellikle küçük sayılarda kullanılır.

def bolenleri_listele(a, b):
bolenler_a = [i for i in range(1, a + 1) if a % i == 0]
bolenler_b = [i for i in range(1, b + 1) if b % i == 0]
ortak_bolenler = set(bolenler_a) & set(bolenler_b)
return max(ortak_bolenler)

Bu yöntem, her iki sayının bölenlerini bulup karşılaştırarak çalışır. Ancak büyük sayılarla uğraşırken zaman ve performans açısından verimli değildir.

Zaman Karmaşıklığı: Bu yöntemin zaman karmaşıklığı O(n)‘dir, burada n, verilen sayılardan birinin değerine bağlıdır.

2. Yöntem: Öklid Algoritması (Euclidean Algorithm)

Öklid algoritması, EBOB hesaplamanın en hızlı ve en etkili yollarından biridir. Algoritmanın temel mantığı, iki sayının EBOB’unun, bu sayılardan büyük olanının küçük olanına bölümünden kalan ile küçük sayı arasında tekrar hesaplanmasıdır. Bu işlem, kalan 0 olana kadar devam eder ve kalan 0 olduğunda küçük sayı EBOB’dur.

Algoritmanın adımları şu şekildedir:

  1. a ve b sayılarının EBOB’u bulunacak.
  2. a’yı b’ye böl ve kalanı bul (r = a % b).
  3. Eğer kalan 0 ise, b EBOB’dur.
  4. Kalan 0 değilse, a = b ve b = r olacak şekilde yeni iki sayı belirle ve aynı işlemi tekrarla.

def ebob_eklid(a, b):
while b != 0:
a, b = b, a % b
return a

Bu yöntem, tekrarlı bölme işlemiyle en büyük ortak böleni hızlı bir şekilde bulur ve büyük sayılar için idealdir.

Zaman Karmaşıklığı: Bu yöntemin zaman karmaşıklığı O(log min(a, b))‘dir, bu da oldukça hızlıdır.

3. Yöntem: Öklid Algoritmasının Rekürsif (Özyinelemeli) Versiyonu

Öklid algoritması aynı zamanda özyinelemeli (recursive) olarak da uygulanabilir. Bu yaklaşımda, algoritma her seferinde kendini tekrar çağırır ve kalan 0 olana kadar işlem devam eder.

def ebob_rekursif(a, b):
if b == 0:
return a
else:
return ebob_rekursif(b, a % b)

Bu algoritmanın çalışma prensibi, döngü yerine fonksiyonun kendisini tekrar tekrar çağırmasıdır. Yine, kalan 0 olduğunda EBOB elde edilmiş olur.

Zaman Karmaşıklığı: Bu da normal Öklid algoritması gibi O(log min(a, b)) zaman karmaşıklığına sahiptir.

Örneklerle EBOB Hesaplama

Örnek 1: 48 ve 18 Sayılarının EBOB’u

48 ve 18 sayılarının EBOB’unu Öklid algoritmasıyla bulalım:

ebob_eklid(48, 18)
  1. 48 % 18 = 12, kalan 12.
  2. 18 % 12 = 6, kalan 6.
  3. 12 % 6 = 0, kalan 0.

Sonuç: 6, EBOB’tur.

Örnek 2: 101 ve 103 Sayılarının EBOB’u

101 ve 103 sayıları asal sayılardır. Asal sayılar birbirine sadece 1 ile bölünebildiği için bu sayıların EBOB’u 1 olacaktır.

ebob_eklid(101, 103)
  1. 101 % 103 = 101, kalan 101.
  2. 103 % 101 = 2, kalan 2.
  3. 101 % 2 = 1, kalan 1.
  4. 2 % 1 = 0, kalan 0.

Sonuç: 1, bu sayıların EBOB’udur.

Zaman Karmaşıklığı Karşılaştırması

Yöntem Zaman Karmaşıklığı Bellek Kullanımı
Bölenleri Listeleme Yöntemi O(n) O(n)
Öklid Algoritması O(log min(a, b)) O(1)
Öklid Algoritmasının Rekürsif Versiyonu O(log min(a, b)) O(log min(a, b))
  • Bölenleri listeleme yöntemi, küçük sayılar için kullanılabilir, ancak büyük sayılarda verimsizdir.
  • Öklid algoritması, oldukça hızlıdır ve büyük sayılar için en iyi sonucu verir.
  • Öklid algoritmasının rekürsif versiyonu, benzer şekilde çalışır ancak özyineleme kullanır, bu da belirli senaryolarda daha sezgisel bir yöntem olabilir.

EBOB’un Gerçek Hayatta Kullanım Alanları

  1. Rasyonel Sayıların Sadeleştirilmesi: EBOB, rasyonel sayıları sadeleştirmek için kullanılır. Örneğin, 12/18 kesiri, EBOB’un 6 olması nedeniyle 2/3 olarak sadeleştirilir.
  2. Kriptografi: EBOB, özellikle RSA gibi kriptografi algoritmalarında kullanılır. Öklid algoritması, büyük asal sayıların hesaplanmasında önemli bir araçtır.
  3. Matematiksel Modelleme: Sayılar arasındaki ilişkilerin modellenmesinde, EBOB gibi kavramlar önemli rol oynar. EBOB, birçok sayısal optimizasyon ve hesaplama probleminde kullanılır.

Sonuç

EBOB hesaplama algoritmaları, matematiksel problemlerin çözümünde temel ve önemli bir yer tutar. Özellikle Öklid algoritması, EBOB hesaplamada en verimli ve yaygın kullanılan yöntemdir. Hem sade hem de hızlı olması nedeniyle büyük sayılarla çalışırken tercih edilir. Algoritmaların farklı versiyonları, kullanım senaryolarına göre seçilebilir ve farklı performans gereksinimlerine yanıt verir.