Стивен Прата - Язык программирования C. Лекции и упражнения (6-е изд.) 2015

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

вывести пользователю приглашение на ввод числа

пока возвращаемым значением функции scanf() является 1 проанализировать число и сообщить результаты вывести пользователю приглашение на ввод числа

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

Далее потребуется выработать план для поиска делителей. Вероятно, наиболее очевидный подход выглядит примерно так:

260 глава 7

for (div = 2; div < num; div++) if (num % div == 0)

printf("%d делится на %d\n", num, div);

В цикле проверяются все числа в промежутке между 2 и num для выяснения, делится ли значение num на них без остатка. К сожалению, такой подход является затратным в смысле времени. Можно поступить гораздо лучше. Рассмотрим, например, процесс поиска делителей для числа 144. Вы обнаруживаете, что 144 % 2 дает 0, т.е. 144 делится на 2 без остатка. Если затем действительно выполнить деление 144 на 2, получится число 72, которое также является делителем 144, так что результатом успешной проверки num % div будут два делителя, а не один. Однако главное достоинство такого подхода кроется в изменении пределов при проверке условия завершения цикла. Чтобы увидеть, как это работает, взгляните на пары делителей, полученные в процессе выполнения цикла: 2, 72; 3, 48; 4, 36; 6, 24; 8, 18; 9, 16; 12, 12; 16, 9; 18, 8 и т.д. Видите, в чем дело? После пары 12, 12 вы начинаете получать те же самые делители (в обратном порядке), которые уже были найдены. Вместо того чтобы продолжать цикл до 143, вы можете остановиться по достижении 12. Это существенно сокращает количество итераций.

Обобщая это открытие, вы увидите, что должны выполнять проверку только до значения, равного квадратному корню num, а не полному num. Для чисел вроде 9 выигрыш не слишком велик, но для чисел порядка 10 000 и выше он огромен. Однако вместо того чтобы иметь дело с квадратными корнями, условие проверки можно выразить следующим образом:

for (div = 2; (div * div) <= num; div++) if (num % div == 0)

printf("%d делится на %d и %d.\n", num, div, num / div);

Если num имеет значение 144, цикл выполняется до div, равного 12. Если num имеет значение 145, цикл выполняется до div, равного 13.

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

Мы должны решить еще две проблемы, после чего можно приступать к программированию. Во-первых, как быть, если проверяемое число является точным квадратом? Сообщение о том, что 144 делится на 12 и еще раз на 12 выглядит неуклюже, поэтому можно предусмотреть вложенный оператор if, в котором проверять равенство div и num / div и в таком случае выводить один делитель вместо двух.

for (div = 2; (div * div) <= num; div++)

{

if (num % div == 0)

{

if (div * div != num)

printf("%d делится на %d и %d.\n", num, div, num / div);

else

printf("%d делится на %d.\n", num, div);

}

}

Управляющие операторы С: ветвление и переходы 261

На заметку!

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

Во-вторых, как узнать, что число является простым? Если значение num является простым, то поток управления программы никогда не попадет внутрь оператора i f. Для решения этой проблемы можно присвоить некоторой переменной какое-то значение, скажем, 1, за пределами цикла и установить ее в 0 внутри if. После завершения цикла можно проверить переменную на предмет равенства 1. Если это так, то вход в тело оператора if не совершался, и число является простым. Переменную подобного рода часто называют флагом.

Традиционно в С для флагов применялся тип int, но здесь отлично подойдет новый тип _Bool. К тому же, включив в программу заголовочный файл stdbool.h, для этого типа вместо ключевого слова _Bool можно использовать bool, а вместо 1 и 0 — идентификаторы true и false. Все эти идеи воплощены в листинге 7.5. Чтобы расширить диапазон, в программе применяется тип long вместо int. (Если ваша система не поддерживает тип _Bool, можете использовать для переменной isPrime тип int и применять 1 и 0 вместо true и false.)