Öklid Algoritması

İki sayının en büyük ortak bölenini (OBEB/EBOB) hesaplar.

Algoritma

gcd(a, b) = gcd(b, a mod b). Base case: gcd(a, 0) = a.

Recursive

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

Iterative

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

Python Builtin

import math
math.gcd(12, 18)  # 6

OKEK (LCM) Hesaplama

lcm(a, b) = a × b / gcd(a, b):

from math import gcd
def lcm(a, b):
    return a * b // gcd(a, b)

# Python 3.9+:
import math
math.lcm(12, 18)  # 36

Performans

O(log(min(a, b))) — iki sayının küçüğünün logaritması kadar adım.

Kullanım Alanları