142_______________________________________________

Прежде всего рассмотрим алгоритм, проверяющий является ли число N простым. Поскольку простое число должно делиться только на вышеуказанные два числа, нужно проверить все остатки от деления проверяемого числа на числа от 2 до N/2 включительно. Если хотя бы один из остатков равен нулю, то это число не простое, а составное, то есть может быть представлено в виде произведения нескольких (не менее двух) простых чисел.

Единица не считается простым числом, потому что при делении любого числа на 1 остаток равен нулю.

Изложенное правило проверки является алгоритмом, поскольку не более чем после N/2-1 операций деления мы получим ответ.

На самом деле ответ может быть получен гораздо раньше, так как деление на число, квадрат которого больше проверяемого числа, не имеет смысла. Ведь если число составное, то оно может быть представлено в виде двух сомножителей. А квадрат наименьшего из них не может быть больше проверяемого числа. Это первый способ повышения эффективности алгоритма проверки.

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

Перейдем к вводу текста подпрограммы-функции из меню Edit посредством NewFUNCTiON. На запрос имени через диалоговое окно введем lsPrime%, что должно означать "суть простое".

Заметим, что имя функции обязательно должно заканчиваться суффиксом, обозначающим тип возвращаемого значения.

Наша функция от формального параметра типа LONG должна возвращать значение типа INTEGER равное 1 для простого числа и о для составного.

Поскольку среда уже ввела автоматически часть первой строки и последнюю, остается ввести недостающее.

FUNCTION lsPrime% (А&) 'начало описания функции 1% = 2 'начальный номер в таблице DO 'начало цикла проверки С& = В(1%) 'выборка из таблицы D& = А& MOD C& 'вычисление остатка IF D& = О THEN EXIT DO

'по нулевому остатку выход из цикла 1% = 1% + 1 'следующий номер в таблице LOOP WHILE A& > C& * C& 'конец цикла проверки IF DS = О THEN lsPrime% = О ELSE IsPrime% = 1

'значение функции END FUNCTION 'конец описания функции

Так как алгоритм проверки уже обсуждался, а текст подпрограммы имеет комментарии, разъясним только формальные подробности подпрограммы. Вычисленное значение функции обязательно должно быть при-