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;
}