Код

static bool isPrime(int n)

{

     // Дуже мале

     if (n <= 1)

          return false;

     // Від 2 до n-1

     for (int i = 2; i < n; i++)

          if (n % i == 0)

               return false;

     return true;

}

Оптимізований 

static bool isPrime(int n) 

{ 

     // Дуже мале

     if (n <= 1) 

          return false; 

     if (n <= 3) 

          return true; 

     // 2 і 3 

     if (n % 2 == 0 || n % 3 == 0) 

          return false; 

     // Від 5 і більше 

     for (int i = 5; i * i <= n; i = i + 6) 

          if (n % i == 0 || n % (i + 2) == 0) 

               return false; 

     return true; 

}