Из математики известно, что наименьший делитель натурального числа, если он существует, меньше либо равен корню квадратному исходного числа. А это означает, что если мы будем искать делитель в диапазоне от 2 до корня квадратного исходного числа, и не найдем его, то можно утверждать, что исходное число является простым!

 d := 2;
 count := 0;
 while (count = 0) and (d <= sqrt(n)) do
  if n mod d = 0
   then inc(count)
   else inc(d);
 if count = 0
  then <Число n простое>
  else <Число n не простое>

Как и в предыдущих случаях мы предполагали, что исходное число больше единицы. Мы пришли практически к совершенному алгоритму проверки простого числа, который выполняет свою работу за приемлемое время. Например, если исходное число равно 1 млрд, то за не более чем 1000 итераций мы может с уверенностью сказать простое ли исходное число или нет!