Решение 50 типовых задач по программированию на языке Pascal Дата размещения сборника в сети

(primes < n) = true – 
входим в цикл 
11 
2 
3 
1 
— 
0 
12-14 
2 
3 
1 
от 1 до 3 
2 
15 
(count = 2) = true 

---

Данил Душистов: «Решение 50 типовых задач по программированию на языке Pascal» 
24 
16 
Вывод числа k (то есть 3) 
17-18 
2 
3 
2 
— 
2 
19 
2 
4 
2 
— 
2 
10 
(primes < n) = false – 
программа завершена 
Как видим, описать действия даже такого элементарного алгоритма и даже при столь малых 
исходных данных – достаточно трудоемкая и трудно проверяемая задача, поэтому очень важно по-
нимать логику самой программы и уметь представлять себе целостную картину ее поведения с ми-
нимальными потребностями в моделировании. 
Вычислительная сложность. Так как в данной задаче в главном цикле присутствует вложен-
ный, в котором происходит ровно k операций (сложность этой конструкции мы определили в 
задаче 
18), 
то его сложность явно не меньше O(n
2
) 
и превышает ее, так как нам явно необходимо выпол-
нить более чем n шагов главного цикла. При этом точность расчета сложности зависит от распреде-
ления простых чисел, которое описывается с помощью достаточно сложных математических прие-
мов и утверждений, так что мы не будем далее рассматривать эту задачу.
Задача № 20. Проверить, является ли заданное натуральное число совершенным 
Формулировка. Дано натуральное число. Проверить, является ли оно совершенным. 
Примечание: совершенным числом называется натуральное число, равное сумме всех своих 
собственных делителей (то есть натуральных делителей, отличных от самого числа). Например, 6 – 
совершенное число, оно имеет три собственных делителя: 1, 2, 3, и их сумма равна 1 + 2 + 3 = 6.