Ortak Katların En Küçüğü (Least Common Multiple , ekok)

Yazan : Şadi Evren ŞEKER

Matematiksel olarak iki tam sayının ortak çarpanlarının (common factors) çarpımından oluşan (common multiple) en küçüğünü bulma işlemidir. Bu işlem için öncelikle sayıların çarpanlarını bulmak sonra bu çarpanlardan ortak olan en küçüğünü almak gerekir.

Örneğin 60 sayısının çarpanları (factors) : 5 3 2 2 olarak yazılabilir yani

60 = 5 x 3 x 2 x 2

Olarak yazılabilir. Buradaki çarpanlar olarak ifade edilen sayılar tamamen tam sayılardır (prime numbers).

Farklı bir sayı olarak 72 sayısını ele alalım:

72 = 3 x 3 x 2 x 2 x 2

Olarak yazılabilir. Bu durumda 72 ve 60 sayılarının en küçük ortak katları (okek, lcm) 2 2 3 olarak bulunur. Yani 72 ve 60 sayılarında 2,2 ve 3 çarpanları ortaktır. Bu durumad 2x2x3 = 12 sayısı hem 60 hem de 72 sayıları için ortak çarpandır. (greatest common divisor, obeb, ortak bölenlerin en büyüğü).

Şimdi 60 ve 72 sayılarının 12 sayısından farklı olmasını sağlayan değerleri bulalım. 12 sayısı 60’ın yarısıdır. Yani 12 sayısını baz alır ve bu sayıya k dersek 60 = 5k olarak yazılabilir. Şimdilik 60 için a ve 72 için b sembollerini kullanalım. Bu durumda

a = 5k

b = 6k

olarak yazılabilir. Buradaki yeni gelen çarpanlar zaten sayıları çarpanlara ayırdığımızda elde ettiğimiz değerlerdir. Şimdi ortak katların en küçüğünü (okek) bulmak için çarpanları değiştiriyoruz. Bu aradığımız okek sayısı için

okek = 6 a = 6 5 k

okek = 5 b = 6 5 k

yukarıda görüldüğü üzere sayıların çarpanlarını değiştirirsek aynı değeri yanı 30k değerini elde etmiş oluyoruz.

Bu işlem için aşağıdaki formülü kullanabiliriz:

LCM ( a,b) = ab / gcd(a,b)

Yani a ve b sayılarının okek’i, a ve b sayılarının çarpımının, a ve b sayılarının OBEB’ine bölümüdür:

Lcm(60,72) = 60 72 / gcd(60,72)

= 4320 / 12 = 360 olarak bulunabilir.

Burada 360 sayısı gerçekten de 72 sayısının 5 misli ve 60 sayısının 6 mislidir.

Bu işlemi programlama dili ile aşağıdaki şekilde yapabiliriz:

#include <stdio.h>

int okek(int a,int b){

   return a*b/obeb(a,b);

}

int obeb(int a,int b)

{

   if(b==0)

        return a;

   else

        return obeb(b,a%b);

}

int main()

{

  int n1,n2;

  printf("OKEK bulmak istediginiz iki sayiyi giriniz:");

  scanf("%d %d",&n1,&n2);

  printf(" %d ve %d sayilarinin okek'i %d 'dir",n1,n2,okek(n1,n2));

  return 0;

}