Сократив число итераций вдвое, мы практически вдвое улучшили алгоритм, но и это еще не предел. А что если исходное число поделилось на два в первой же итерации, то зачем тогда дальнейшая проверка? Следовательно, откажемся от цикла с параметром в пользу цикла с условием:

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

Это уже что-то! Наш алгоритм достаточно быстро проверяет, является ли число простым, так как большая часть чисел не простые, но если так встречается большое простое число, то проверка идет до конца и значительно долго!
Нет ли способа и тут сократить число итераций? Оказывается есть!