Практикум по курсу "Алгоритмизация и программирование". Часть 1. Андрианова А.А - 34 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

Рис.3.4. Блок-схема решения задачи о высоте цилиндра.
Задача 4. Распечатать все простые числа до 100.
Число 2 распечатываем без проверки, так как это единственное простое
четное число. Все остальные нечетные числа проверяем на “простоту”. Для
проверки простоты числа k требуется исследовать в качестве делителей все
нечетные числа от 3 до k/2. Если найдется хотя бы один делитель, то число k
не является простым. Факт нахождения такого делителя можно определить с
помощью приема, называемого “использованием флажка”. Флажком является
переменная, которая имеет всего два значения. Одно из них соответствует
состоянию “истина”, другое – “ложь”. Значение переменной меняется при
выполнении определенных условий (в данной задаче – при нахождении
делителя числа k). Проверив все возможные делители, по значению
переменной-флажка определяем, выполнилось ли требуемое условие.
Заметим, что для проверки на простоту числа k достаточно было
проверить на делимость все нечетные числа до квадратного корня из k.
Например, если k =15, то вовсе необязательно проверять в качестве делителя
число 5. Поскольку k=5·3, то меньший делитель (3) будет найден на более
ранних итерациях. Поэтому проверку следует осуществлять до квадратного
корня из k, например, 25=5·5.
Блок-схема показана на Рис.3.5. 
            Рис.3.4. Блок-схема решения задачи о высоте цилиндра.

    Задача 4. Распечатать все простые числа до 100.
    Число 2 распечатываем без проверки, так как это единственное простое
четное число. Все остальные нечетные числа проверяем на “простоту”. Для
проверки простоты числа k требуется исследовать в качестве делителей все
нечетные числа от 3 до k/2. Если найдется хотя бы один делитель, то число k
не является простым. Факт нахождения такого делителя можно определить с
помощью приема, называемого “использованием флажка”. Флажком является
переменная, которая имеет всего два значения. Одно из них соответствует
состоянию “истина”, другое – “ложь”. Значение переменной меняется при
выполнении определенных условий (в данной задаче – при нахождении
делителя числа k). Проверив все возможные делители, по значению
переменной-флажка определяем, выполнилось ли требуемое условие.
    Заметим, что для проверки на простоту числа k достаточно было
проверить на делимость все нечетные числа до квадратного корня из k.
Например, если k =15, то вовсе необязательно проверять в качестве делителя
число 5. Поскольку k=5·3, то меньший делитель (3) будет найден на более
ранних итерациях. Поэтому проверку следует осуществлять до квадратного
корня из k, например, 25=5·5.
     Блок-схема показана на Рис.3.5.

Страницы