i21прим/Docu.Пошаговая разработка/3. Простые.odc

3. Пошаговая разработка: Определение простоты числа 

Задача. Разработать процедуру для определения простоты заданного целого большего единицы

Решение

ЧастьА  Постановка задачи. Проектирование интерфейса
ЧастьБ  Разработка тела процедуры. Сведение задачи к более простой подзадаче
ЧастьВ  Перевод текстовых фрагментов на Компонентный Паскаль
ЧастьГ  Выход из процедуры
ЧастьД  Демонстрация работы
ЧастьЕ  Упрощение кода
ЧастьЖ Оптимизация: сокращение количества шагов цикла
Парадокс Почему порочна преждевременная оптимизация


Часть А. Постановка задачи. Проектирование интерфейсов

Эта часть выполняется во многом так же, как и в первомпримере. Отличия в следующем. Во-первых, модулю дадим другое имя. Например, пусть полное имя будет i21примПростые, и тогда имя файла будет Простые.

Во-вторых, сигнатура процедуры будет иной. Процедура должна отвечать на некий вопрос относительно задаваемого целого числа. Самый естественный способ передавать в процедуру это число  с помощью параметра типа INTEGER (как наиболее универсального из целых базовых типов Компонентного Паскаля). Так как процедура должна давать ответ типа да/нет, причем только один, то пусть она будет процедурой-функцией, а тип возвращаемого значения  BOOLEAN.

Другие варианты. Целое число можно было бы передавать через целую переменную, определенную на уровне модуля и доступную извне модуля для записи, т.е. отмеченную символом полного экспорта *. 
Результат можно было бы передавать с помощью аналогичной глобальной переменной, причем эту переменную имело бы смысл сделать видимой извне только для чтения, т.е. отметить символом частичного экспорта -. 
Наконец, в некоторых ситуациях могло бы оказаться предпочтительным, чтобы результат был целым  например, равным 0 или 1 в случае, соответственно, отрицательного или положительного ответа на вопрос о простоте числа. 
Однако все эти варианты полезны лишь в каких-то особых ситуациях, не предусмотренных в условии задачи. Поэтому будем придерживаться наиболее универсального варианта.

Итак, заготовка модуля и процедуры будет такой (строка IMPORT пока опущена):

MODULE  i21примПростые;
	
	PROCEDURE Простое* ( n: INTEGER ): BOOLEAN;
		VAR  
	BEGIN
		
	END Простое;
	
END  i21примПростые.

Звездочка экспорта в заголовке процедуры поставлена, чтобы можно было ею пользоваться из любых других программ, в том числе из других модулей.
Имя экспортированной процедуры выделено жирным шрифторм (Ctrl+B или  выполнить команду меню Шрифт --> Жирный), потому что информация об экспорте очень важна.

Немедленно скомпилируем модуль (Ctrl+K). 
Получим сообщение об ошибке  черный квадратик сразу после ключевого слова BEGIN, а внизу экрана слева  сообщение "функция без RETURN".
В самом деле, если определена процедура-функция, то в ее теле должен обязательно быть хотя бы один оператор возврата RETURN. 

Вставим оператор RETURN последним оператором в пока еще пустом теле процедуры (поставим курсор в пустую строку  кликнуть примерно под словом VAR, нажмем клавишу ввода (Enter), напечатаем слово return и нажмем F5). 
Модуль примет след. вид:

MODULE  i21примПростые;
	
	PROCEDURE Простое* ( n: INTEGER ): BOOLEAN;
		VAR  
	BEGIN
		
		RETURN  
	END Простое;
	
END  i21примПростые.

RETURN автоматически выделилось жирным шрифтом (это сработала процедура, вызванная нажатием F5), т.к. это полезно делать для выявления структуры программы. Компилятору это не важно.

Пустая строка перед RETURN напоминает о том, что там должны быть операторы, реализующие содержательную часть алгоритма.

Скомпилируем модуль (Ctrl+K). Возникнет сообщение об ошибке  черный квадратик сразу после слова RETURN, а внизу экрана слева текст "тип результата выражения отличается от типа результата процедуры".

Действительно: раз процедура была объявлена как процедура-функция, возвращающая значение какого-то типа (в данном случае BOOLEAN), то по правилам Компонентного Паскаля после любого оператора RETURN в теле процедуры должно стоять выражение того же самого типа (BOOLEAN).
Какое выражение поставить?

У нас пока нет конкретного алгоритма вычисления ответа, поэтому пока поставим "затычку"  простейшее выражение булевского типа, состоящее из одной константы FALSE (в месте курсора печатаем false и нажимаем F5).
Чтобы не забыть в дальнейшем про эту затычку, покрасим ее в красный цвет (двойной клик по FALSE, Шрифт > Красный).

Проверка входных данных. Наконец, в задаче есть еще одно условие: оговаривается, что проверяемые числа больше единицы. А как должна вести себя процедура, если на вход поступает число, не удовлетворяющее этому условию?
В этом случае, вообще говоря, возможны следующие варианты:
а) аварийная остановка;
б) возврат предопределенного значения;
в) сообщение пользователю (в рабочем журнале или в статусной строке или в виде диалогового сообщения);
г) присваивание специального значения некоторой глобальной переменной.

Чтобы сделать выбор  особенно это касается вариантов б)-г)  нужно больше знать о том контексте, в котором будет работать программа. Без дополнительной информации выберем вариант а), который является, во-первых, простейшим для реализации, во-вторых, наиболее жестким, т.е. в максимальной степени ограничивающий распространение ошибки (если считать ошибкой нарушение условия о том, что проверяемое число больше единицы).
Реализация варианта а) сводится к вызову стандартной процедуры ASSERT( n>1) ("убедиться, что n>1") в качестве первого исполняемого оператора в теле разрабатываемой процедуры. Тогда невыполнение условия n>1 вызовет аварийную остановку программы.

В итоге получаем получаем следующую заготовку модуля:

MODULE  i21примПростые;
	
	PROCEDURE Простое* ( n: INTEGER ): BOOLEAN;
		VAR  
	BEGIN
		ASSERT( n>1 );
		
		RETURN  FALSE
	END Простое;
	
END  i21примПростые.

Теперь модуль должен компилироваться без ошибок. 


Часть Б. Разработка тела процедуры

Отталкиваемся от определения простоты: число n является простым, если оно не делится ни на что, кроме 1 и себя.

В случах, когда нужно вычислять логические значения, полезно бывает "вывернуть" условие задачи, т.е. найти его отрицание. В нашем случае это будет выглядеть так: число n не является простым, если у него есть хотя бы один делитель m, отличный от него самого и от 1. Поэтому если нам удастся найти такой делитель m, то n не может быть простым. 
Таким образом, задача сводится к поиску какого-нибудь делителя для n в сегменте от 2 до n-1. Если поиск окажется удачным  число не является простым. Если неудачным  число n простое.

Как найти делитель в сегменте от 2 до n-1?
Как вообще искать объект с заданными свойствами в некотором множестве объектов? Простейшая и универсальная стратегия  перебор.
Поэтому будем перебирать все числа из сегмента от 2 до n-1, пока не найдем делитель для n.

Стандартные средства перебора  циклы. Их есть несколько видов. В нашем случае мы должны прекратить перебор, как только объект с заданными свойствами будет обнаружен, а стандартное средство подобного перебора  цикл-пока. Такой цикл можно записать так:

		WHILE (кандидат находится в допустимом диапазоне) & ~(кандидат обладает нужным свойством) DO
			переход к очередному кандидату
		END;

Чтобы напечатать это, нужно сначала напечатать while, нажать F5, на месте курсора напечатать первую пару круглых скобок, напечатать их содержимое, потом после скобок пробел, &, пробел, ~, вторую пару скобок, и потом содержимое скобок. Затем текст в теле цикла.

Заметим, что в языках программирования скобки ходят парами: для каждой открывающей должна быть и закрывающая. Поэтому полезно выработать привычку ставить скобки парами сразу  открывающую вместе с закрывающей  ДО того, как заполняется содержимое скобок. Это предотвратит целый класс синтаксических ошибок и сэкономит время при разработке программ.
Такое же правило применимо и в других случаях  при написании комментариев, индексов массивов (пары квадратных скобок), "скобок" типа RECORD END и т.д. Впрочем, случаи вроде RECORD END обычно автоматически обрабатываются правильно при использовании клавиши F5 в нашей конфигурации Блэкбокса.

Если перевести ключевые слова на русский язык, то получится следующее:

		ПОКА (кандидат находится в допустимом диапазоне) И неверно, что (кандидат обладает нужным свойством) ДЕЛАТЬ
			переход к очередному кандидату
		КОНЕЦ;

То, что стоит между WHILE и DO (ПОКА и ДЕЛАТЬ)  логическое выражение. При этом фраза "неверно, что"  это в точности операция логического отрицания, которая в Компонентном Паскале обозначается символом ~. А связка И является логической операцией, обозначаемой в Компонентном Паскале символом &.
	
Напомним, что в Компонентном Паскале вычисление второго операнда логической операции & (И), как и ИЛИ (OR), не выполняется, если значение операции может быть определено по первому операнду. 
Именно поэтому при поиске вроде нашего сначала всегда ставится проверка того, входит ли очередной проверяемый кандидат в допустимый диапазон, т.к. если это не так, вторая проверка вообще может не иметь смысла и даже приводить к аварийной остановке.

Смысловое замечание. Пара логических условий, соединенных так, как это сделано в приведенном цикле, типична для задач поиска. При этом смысл задачи отражает второе условие  в скобках после пары логических операций & ~. Первое условие имеет более технический характер и нужно для правильного выхода из цикла.

Поскольку каждый кандидат проверяется совершенно независимо от остальных, мы можем перебирать объекты-кандидаты в произвольном порядке и при этом использовать одну и ту же переменную для их хранения: так и назовем ее, "кандидат". Нужно объявить ее в разделе объявлений, т.е. после ключевого слова VAR. Сделав это, получим след. процедуру:

	PROCEDURE Простое* ( n: INTEGER ): BOOLEAN;
		VAR  кандидат: INTEGER;
	BEGIN
		ASSERT( n>1 );
		кандидат := начальное значение;
		WHILE  (кандидат находится в допустимом диапазоне) & ~(кандидат делит n)  DO
			переход к очередному кандидату
		END;		
		RETURN  FALSE
	END Простое;

Конструкция WHILE ... DO оказалась слишком длинной и не поместилась на одной строке. Это особой роли не играет, но мешает схватывать конструкцию при чтении. Поэтому сформатируем строку следующим образом (кликнуть непосредственно перед &, нажать ввод, потом дважды Tab):

	PROCEDURE Простое* ( n: INTEGER ): BOOLEAN;
		VAR  кандидат: INTEGER;
	BEGIN
		ASSERT( n>1 );
		кандидат := начальное значение;
		WHILE  (кандидат находится в допустимом диапазоне) 
				& ~(кандидат делит n)  DO
			переход к очередному кандидату
		END;		
		RETURN  FALSE
	END Простое;

Компилировать модуль здесь бессмысленно, т.к. имеются четыре чисто текстовых фрагмента. Их надо сначала перевести на Компонентный Паскаль. Это сделать несложно, причем эти фрагменты достаточно просты и уже не потребуют введения вспомогательных процедур.


Часть В. Перевод текстовых фрагментов на Компонентный Паскаль

Начнем с простейшего: "кандидат находится в допустимом диапазоне".
Допустимый диапазон  от 2 до n-1 включительно. 
То есть кандидат должен быть больше либо равен 2 и меньше либо равен n-1. 
Перевод этого условия на Компонентный Паскаль не представляет трудностей:
	
	(кандидат >= 2) & (кандидат <= n - 1)

Как теперь перевести фразу "кандидат делит n"?
Мы должны начать с двух переменных  кандидат и n  и проделать некоторое вычисление, в результате которого должно получиться логическое значение, равное TRUE, если кандидат делит n, и FALSE в противном случае.

Какие вычисления вообще можно проделать в Компонентном Паскале с двумя целыми числами? 
Есть пять арифметических операций (+, -, *, DIV, MOD)  все они дают в результате целое число (точнее, результат будет иметь тип INTEGER, если операнды имеют тип INTEGER).
Есть также шесть операций сравнения (=, #, >, <, >=, <=)  они дают результат типа BOOLEAN.
Можно применить и операцию вещественного деления /  она даст результат типа REAL.
Применяя метод пристального разглядывания, найдем, что к делимости двух целых чисел самое непосредственное отношение имеет операция MOD: выражение  (n MOD кандидат) дает остаток от деления n на кандидата, и если этот остаток равен нулю, то кандидат делит n.
Таким образом, искомое выражение представляет собой выражение
	(n MOD кандидат) = 0
в котором сначала вычисляется выражение в скобках, а потом получившееся число сравнивается с нулем.
Если получается TRUE, то кандидат делит n, что и требуется.

Процедура принимает следующий вид:

	PROCEDURE Простое* ( n: INTEGER ): BOOLEAN;
		VAR  кандидат: INTEGER;
	BEGIN
		ASSERT( n > 1 );
		кандидат := начальное значение;
		WHILE  ( (кандидат >= 2) & (кандидат <= n - 1) ) 
				& ~( (n MOD кандидат) = 0 )  DO
			переход к очередному кандидату
		END;		
		RETURN  FALSE
	END Простое;

Осталось два текстовых фрагмента, описывающих стратегию перебора кандидатов. 
Мы намеренно зазрабатываем программу так, что выбор стратегии перебора совершенно не зависим от структуры проверок в цикле. 
Это позволяет лучше выявить в структуре программы общие моменты, не зависящие от специфики задачи.

Итак, мы должны перебрать кандидаты так, чтобы не пропустить ни одного потенциального делителя.

Поскольку кандидаты заполняют сегмент от 2 до n - 1, то естественно начать с наименьшего значения, т.е. двойки, а в качестве очередного кандидата брать число, на единицу большее.
То есть сделаем такие замены:
	начальное значение > 2, 
	переход к очередному кандидату  > кандидат := кандидат + 1

Замечание. Точку с запятой после этого оператора ставить можно, но не обязательно; в старом Паскале ее там ставить было нельзя. См. об этом здесь.

Важно теперь понять, всегда ли будет обеспечен выход из цикла. Поскольку значения, которые принимает кандидат, на каждом шаге меняются в одну сторону  растут,  то рано или поздно кандидат обязательно выйдет из допустимого диапазона, то есть первое условие в охране цикла гарантирует его завершение. Разумеется, выход из цикла может произойти и раньше  по второму условию охраны. Смысл всего этого мы обсудим дальше. Пока важно убедиться, что выход из цикла обеспечен.

В итоге модуль примет следующий вид:

MODULE  i21примПростые;
	
	PROCEDURE Простое* ( n: INTEGER ): BOOLEAN;
		VAR  кандидат: INTEGER;
	BEGIN
		ASSERT( n>1 );
		кандидат := 2;
		WHILE  ( (кандидат >= 2) & (кандидат <= n - 1) ) 
				& ~( (n MOD кандидат) = 0 )  DO
			кандидат := кандидат + 1
		END;		
		RETURN  FALSE
	END Простое;
	
END  i21примПростые.

Теперь его можно скомпилировать и устранить опечатки.

Часть Г. Выход из процедуры

Но пока наша процедура, хотя и компилируется без ошибок, всегда возвращает значение FALSE, независимо от результата поиска делителя в цикле. Нужно это поправить.

Рассмотрим подробнее, в каком состоянии завершается цикл.
Очевидно, цикл WHILE завершается, когда не выполнено условие в охране цикла. То есть после завершения цикла выполнено отрицание охраны. 
Запишем и упростим соответствующиее логическое выражение (записывать его будем, выявляя структуру операций):

		~( 
			  ( (кандидат >= 2) & (кандидат <= n - 1) ) 
			  & ~( (n MOD кандидат) = 0 ) 
		   )

Используем закон де Моргана для самого внешнего отрицания (законы де Моргана остаются справедливы для "компьютерных" вариантов логических операций):

			  ~( (кандидат >= 2) & (кандидат <= n - 1) ) 
			  OR ( (n MOD кандидат) = 0 ) 
		
Получившийся результат можно переформулировать словами так:
	либо неверно, что (кандидат находится в допустимом диапазоне),
	либо в противном случае он является делителем для n.

Первый случай означает, что делителей не найдено, т.е. число n простое. 
Второй случай означает, что в допустимом диапазоне найден делитель, т.е. число n не является простым.

Таким образом, ответ на вопрос, является ли n простым, оказывается в точности равен ответу на вопрос, неверно ли, что (кандидат находится в допустимом диапазоне) после выхода из цикла.
То есть в качестве возвращаемого значения после оператора RETURN вместо FALSE мы можем прямо подставить выражение 

	неверно, что (кандидат находится в допустимом диапазоне)

или на языке Компонентный Паскаль:

	~( (кандидат >= 2) & (кандидат <= n-1) )

Во избежание опечаток выражение следует просто аккуратно скопировать из цикла с помощью Ctrl+C, Ctrl+V):
Выражение можно упростить, избавившись от отрицания с помощью закона де Моргана, но это не обязательно  и вдобавок чревато ошибками; см. об этом далее разделД.

Окончательно модуль выглядит так:

MODULE  i21примПростые;
	
	PROCEDURE Простое* ( n: INTEGER ): BOOLEAN;
		VAR  кандидат: INTEGER;
	BEGIN
		ASSERT( n>1 );
		кандидат := 2;
		WHILE  ( (кандидат >= 2) & (кандидат <= n - 1) ) 
				& ~( (n MOD кандидат) = 0 )  DO
			кандидат := кандидат + 1
		END;		
		RETURN  ~( (кандидат >= 2) & (кандидат <= n - 1) )
	END Простое;
	
END  i21примПростые.


Д. Демонстрация работы

Для демонстрации работы процедуры напишем отдельный модуль (в виде отдельного документа) с тестирующей процедурой, которая просто печатает все простые числа из заданного интервала в рабочий журнал:

MODULE  i21примПростыеПечать;
	IMPORT  StdLog,  i21примПростые;
	
	PROCEDURE Выполнить* ( n, m: INTEGER );
		VAR  i: INTEGER;
	BEGIN
		StdLog.Ln;
		StdLog.String("все простые числа в интервале от");
		StdLog.Int( n );
		StdLog.String(" до");
		StdLog.Int( m );
		StdLog.String(":");
		StdLog.Ln;
		FOR  i := n  TO  m  DO
			IF  i21примПростые.Простое( i ) THEN
				StdLog.Int( i )
			END
		END;
		StdLog.Ln
	END Выполнить;
	
END  i21примПростыеПечать.

"i21примПростыеПечать.Выполнить(2, 50)"

Чтобы выполнить процедуру, достаточно кликнуть по коммандеру. Меняя значения чисел, можно менять диапазон печатаемых простых чисел.

Е. Упрощение кода

Внимание!  Давно известно, что бОльшая часть программистских проблем связана с преждевременными попытками сделать программу быстрее и вообще "эффективнее" за счет возни с мелкими трюками в тексте программы. 
Интересно, что бОльшая часть таких попыток к заметному эффекту не приводит  а нередко эффект получается вообще обратный. На самом деле определить, где реально программа проводит большую часть времени, нелегко без конкретных измерений (т.наз. профилирование; см. соотв. команды в меню Программирование).
Поэтому следует всемерно сопротивляться такого рода манипуляциям с кодом, стремясь прежде всего к "дубовой надежности" и "очевидной правильности" уже работающей программы  и именно это должны поощрять преподаватели.

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

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

Однако явные упрощения  если таковые находятся  могут быть и полезны, если они упрощают код без нарушения его "очевидной правильности".

Что можно упростить в этой программе?
Прежде всего это логические выражения. Они довольно сложны.
Метод пристального разглядывания показывает, что условие кандидат >=2 всегда выполнено, т.к. мы начинаем со значения 2 и только увеличиваем значение кандидата. 
Поэтому упростим оба логических выражения, заменив обсуждаемое условие на TRUE и отбросив его по правилу TRUE & X = X. 
Это "хорошее" упрощение, т.к. приводит просто к отбрасыванию целого сравнения без ощутимого затемнения смысла программы.
Заголовок цикла станет таким:

		WHILE  (кандидат <= n - 1) & ~( (n MOD кандидат) = 0 )  DO

А оператор RETURN станет таким:

		RETURN  ~(кандидат <= n - 1)

Можно упростить выражение в RETURN, избавившись от отрицания, но это разрушит очевидное равенство выражения в скобках первому операнду охраны цикла. 
Можно также упростить второе сравнение в охране цикла  его смысл останется ясен:

	~( (n MOD кандидат) = 0 )  заменится на  ( (n MOD кандидат) # 0 )

В итоге получаем:

MODULE  i21примПростые;
	
	PROCEDURE Простое* ( n: INTEGER ): BOOLEAN;
		VAR  кандидат: INTEGER;
	BEGIN
		ASSERT( n>1 );
		кандидат := 2;
		WHILE  (кандидат <= n - 1) & ~( (n MOD кандидат) = 0 )  DO
			кандидат := кандидат + 1
		END;		
		RETURN  ~(кандидат <= n - 1)
	END Простое;
	
END  i21примПростые.


Ж. Оптимизация: сокращение количества шагов цикла

В данной процедуре возможна одна оптимизация, которая достаточно проста и практически не меняет структуру кода. Эта оптимизация связана не с мелкой оптимизацией кода, а с существом задачи (именно такие оптимизации наиболее полезны).

Замечание. Нахождение таких оптимизаций не относится собственно к программированию и выходит за пределы возможностей "чистых" программистов-профессионалов. Оно может произойти лишь в голове специалиста, четко понимающего как предметную область (в данном случае элементарную арифметику), так и методы построения алгоритмов. На обучение именно таких специалистов в первую очередь и нацелен проект Информатика-21. 

В самом деле, пристальное разглядывание процедуры говорит о том, что все вычисления используют лишь "быстрые" операции, и важнейшая возможность существенно ускорить цикл состоит в том, чтобы как-то сократить количество повторений цикла. 
Далее, пристальное разглядывание цикла показывает, что фактически цикл находит наименьший делитель для n. Но наименьший делитель не может превосходить квадратный корень из n. Другими словами, проверять кандидаты, превосходящие корень из n, нет нужды. Это сокращает количество шагов цикла  и время выполнения процедуры  на множитель, равный корню из n. 
Для n = 1000000 имеем ускорение в 1000 раз. Овчинка выделки стоит.

Разумеется, вычисление такой стандартной функции, как квадратный корень в Блэкбоксе есть. Изучение библиотеки Блэкбокса показывает, что там есть модуль Math, содержащий процедуры вычисления элементарных функций, в том числе процедура Sqrt, вычисляющая квадратный корень.
Список процедур, предоставляемых модулем Math (точнее, список их сигнатур), можно получить, дважды кликнув мышкой по имени модуля (например, в предыдущей строчке) и нажав Ctrl+D (или командой меню Инфо > Клиентский интерфейс).

Имена функций в основном самоочевидны. Обнаруживаем, что нужная сигнатура имеет вид

	PROCEDURE Sqrt (x: REAL): REAL;
	
Чтобы использовать эту функцию в нашем модуле, следует импортировать модуль Math. это достигается добавлением строки
	
	IMPORT  Math; 
	
сразу после заголовка модуля. После этого нужное нам значение в теле процедуры Простое будет даваться выражением Math.Sqrt(n).

Следует разобраться с типами значений. 
Сигнатура процедуры Sqrt показывает, что она принимает аргумент типа REAL. 
Но у нас n имеет тип INTEGER. Компонентный Паскаль разрешает подставлять значения INTEGER там, где требуется REAL, при этом будет автоматически произведено надлежащее преобразование типа. (Естественное преобразование INTEGER в REAL не приводит к потере информации и поэтому разрешено как автоматическое. Напомним, что тип REAL в Компонентном Паскале соответствует арифметике с плавающей точкой двойной точности в других языках.)

Значение функции Math.Sqrt тоже имеет тип REAL. 
Предположим, что мы сохранили его в переменной корень (типа REAL) до выполнения цикла. Тогда следует всюду изменить верхнюю границу допустимого диапазона для переменной кандидат, заменив:

MODULE  i21примПростые;
	IMPORT Math;
	
	PROCEDURE Простое* ( n: INTEGER ): BOOLEAN;
		VAR  кандидат: INTEGER;  корень: REAL;
	BEGIN
		ASSERT( n>1 );
		кандидат := 2;
		корень := Math.Sqrt( n );
		WHILE  (кандидат <= корень) & ~( (n MOD кандидат) = 0 )  DO
			кандидат := кандидат + 1
		END;		
		RETURN  ~(кандидат <= корень)
	END Простое;
	
END  i21примПростые.

Программа компилируется без ошибок и работает, похоже, правильно. 


Парадокс. Почему порочна преждевременная априорная оптимизация

Описанную оптимизацию часто кодируют чуть более "грамотно". При этом исходят из следующих умозрительных соображений о поведении программы. 

Что происходит при сравнении кандидат <= корень, где левый операнд имеет тип INTEGER, а правый  REAL?
Правила Компонентного Паскаля построены так, чтобы исключить неконтролируемую потерю информации. Это возможно, только если в таком сравнении операнд типа INTEGER преобразуется к типу REAL. 
Именно это и имеет место  причем на каждом шаге цикла. Кроме того, на машинном уровне операция сравнения обычно подразумевает вычитание операндов и сравнение результата с нулем. И обычно выполнение отдельно операции вычитания для значений INTEGER быстрее, чем для значений REAL.
Таким образом, имеет смысл избавиться от всех значений типа REAL в цикле.

Cоображения кажутся "очевидно правильными"  и тем не менее результат может оказаться прямо противоположным. Чтобы исследовать вопрос, выполним эту оптимизацию. Это делается так (соответствующий вариант процедуры Простое назовем Простое2).

Объявим переменную корень как INTEGER, а в правой части присваивания поставим целую часть от вещественного значения:

	корень := SHORT( ENTIER( Math.Sqrt( n ) );
	
Пояснения. Сначала вычисление Math.Sqrt( n ) дает значение REAL. Применение определенной в языке функции ENTIER выбирает целую часть вещественного результата и возвращает ее как значение типа LONGINT. Но т.к. n имело тип INTEGER, то и целая часть его квадратного корня попадет в диапазон типа INTEGER, поэтому получившееся значение типа LONGINT можно "сократить" до типа INTEGER с помощью функции SHORT.

Никаких других изменений в тексте процедуры не требуется.

Нужно только проверить правильность замены вещественного числа на его целую часть в дальнейших неравенствах. Целая часть может быть меньше, чем исходное вещественное значение, и поэтому сравнение <= могло бы нарушиться. Но в левой части сравнения всегда стоит целое значение, так что худшее, что может случиться, это фактическое строгое неравенство превратится в равенство. Но результат нестрого неравенства от этого не пострадает.  (Пример: 2 <= 2.236, где правая часть соответствует квадратному корню из 5.)

Для этой вспомогательной задачки создадим новый модуль, включим в него новый вариант процедуры и добавим две тестирующие процедуры, каждая из которых вызывает свой вариант процедуры Простое миллион раз (нужно не забыть импортировать уже написанный модуль):

MODULE  i21примПростыеОпт;
	IMPORT Math, i21примПростые;
	
	PROCEDURE Простое2* ( n: INTEGER ): BOOLEAN;
		VAR  кандидат: INTEGER;  корень: INTEGER;
	BEGIN
		ASSERT( n>1 );
		кандидат := 2;
		корень := SHORT( ENTIER( Math.Sqrt( n ) ) );
		WHILE  (кандидат <= корень) & ~( (n MOD кандидат) = 0 )  DO
			кандидат := кандидат + 1
		END;		
		RETURN  ~(кандидат <= корень)
	END Простое2;
	
	PROCEDURE Test*;
		CONST  миллион = 1000000;
		VAR  res: BOOLEAN;  n: INTEGER;
	BEGIN
		FOR  n := миллион  TO 2*миллион  DO
			res := i21примПростые.Простое( n )
		END;
	END Test;
	
	PROCEDURE Test2*;
		CONST  миллион = 1000000;
		VAR  res: BOOLEAN;  n: INTEGER;
	BEGIN
		FOR  n := миллион  TO 2*миллион  DO
			res := Простое2( n )
		END;
	END Test2;
	
END  i21примПростыеОпт.

Воспользуемся возможностью Блэкбокса выполнять программы с замером времени. 

Напишем прямо в данном тексте полное имя тестирующей процедуры для "медленного" варианта  с переменной корень, объявленной как REAL:
	
	i21примПростыеОпт.Test

Отметив мышкой полное имя, выполним команду меню 
Программирование > Выполнить с замером времени.
Через некоторое время (около 5 сек. на Pentium III/866) в рабочем журнале появится время выполнения вызванной процедуры в тысячных долях секунды. Повторим это действие несколько раз  времена будут слегка меняться, но оставаться в некотором узком диапазоне (в нашем случае 4843-4860 миллисек.)

Теперь точно так же измерим второй, предположительно более быстрый, вариант процедуры, в котором из цикла исключена арифметика вещественных чисел:

	i21примПростыеОпт.Test2

В нашем случае получается диапазон 5031-5047 миллисек. Другими словами: 

	"Быстрая" версия оказалась определенно медленней!

Хотя разница невелика  всего 4%  но ее знак противоположен ожиданиям.

Для наблюденного эффекта можно придумать объяснение (паралеллизм работы блоков процессора, ответственных за вычисления с целыми и вещественными числами)  но главное, что наш эксперимент иллюстрирует давно известный факт:
	
	Заранее правильно предсказать эффект "мелкой" оптимизации нелегко, 
	а величина его скорее всего ничтожна, 
	так что затрачиваемые усилия окупятся 
	лишь в исключительных случаях.
	
	В подавляющем же большинстве случаев 
	прямым и немедленным результатом умозрительной "оптимизации" 
	будет усложнение и затемнение кода.
	Это с самого начала затруднит разработку, 
	лишая программиста главного ресурса  времени  
	для серьезного анализа уже работающей программы.