Tanım: Sadece 1′ ve kendisine tam bölünebilen pozitif tam sayılara asal sayı denir. Peki bir sayının asal olup olmadığını nasıl kontrol edebiliriz? Sayımız n olsun. Bu durumda 2 ile n-1 arasında tüm tam sayılara tam bölünüp bölünmediğini kontrol ederek asal olup olmadığını söyleyebiliriz. Bu durumda (n-3) tane bölme işlemi yapmamız gerekiyor.

Bilgi: Tek çift asal sayı 2′dir. Bu bilgi ışığında; yaptığımız bölme işlemlerinin sayısını yarıya indirebiliriz. 2 hariç çift sayılar için asallık kontrolü yapmamıza gerek yok.

Teorem: Bir sayısı kareköküne kadar hiçbir sayıya tam bölünmüyorsa o sayı asaldır. Bu durumda yaptığımız bölme işlemlerinin sayısı baya bir azalacak, çünkü sadece çift olmayan ve karekök n’den küçük tam sayılar için bu testi yapmamız yeterli olacaktır.

public bool isPrime(int n)
{
  if (n < 2) return false;
  for (int i = 2; i*i <= n; i+=2)
    if (n % i == 0) return false;
  return true;
}

Hepiniz DVD’leri bilirsiniz, 8 gb civarında bilgi saklayabilen CD’lerin gelişmiş türevleridir ve sinema endüstrisinde sıkça kullanılırlar. DVD’lerin 40/1 oranında sıkıştırma yapması için MPEG-2 algoritması geliştirilmiştir. Daha sonradan daha iyi bir algoritma olan MPEG-4 (DivX) geliştirildi. Devam…