Решение задачи №4037
Условие задачи №4037:
Дано натуральное число. Вывести на экран все простые числа до заданного включительно.Решение
Описание отсутствуетРешение:
В решении данной задачи используется решение предыдущей.
Нам необходимо произвести тест простоты числа, который был описан в решении предыдущей задачи следующим кодом (обозначим его как код 1):
1 2 3 4 5 | count := 0;for i := 1 to n do begin if n mod i = 0 then inc(count)end;writeln(count = 2); |
Здесь n – проверяемое на простоту число. Напомним, что данный фрагмент кода в цикле проверяет, делится ли n на каждое i в отрезке от 1 до самого n, и если n делится на i, то увеличивает счетчик count на 1. Когда цикл заканчивается, на экран выводится результат проверки равенства счетчика числу 2.
В нашем же случае нужно провести проверку на простоту всех натуральных чисел от 1 до заданного числа (обозначим его как n). Следовательно, мы должны поместить код 1 в цикл по всем k от 1 до n. Также в связи с этим необходимо заменить в коде 1 идентификатор n на k, так как в данном решении проверяются на простоту все числа k. Кроме того, теперь вместо вывода ответа о подтверждении/опровержении простоты k необходимо вывести само это число в случае простоты:
1 | if count = 2 then write(k, ' '); |
Обобщая вышесказанное, приведем алгоритм на естественном языке:
1) Ввод n;
2) Запуск цикла, при котором k изменяется от 1 до n. В цикле:
1. Обнуление переменной count;
2. Запуск цикла, при котором i изменяется от 1 до k. В цикле:
Если k делится на i, то увеличиваем значение переменной count на 1;
3. Если count = 2, выводим на экран число k и символ пробела.
Код:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | program PrimesToN; var i, k, n, count: word; begin readln(n); for k := 1 to n do begin count := 0; for i := 1 to k do begin if k mod i = 0 then inc(count) end; if count = 2 then write(k, ' ') endend. |
Вычислительная сложность:
В данной задаче мы впервые столкнулись с вложенным циклом (когда один цикл запускается внутри другого). Это означает, что наш алгоритм имеет нелинейную сложность (при которой количество выполненных операций равно размерности исходных данных (в нашем случае это n – количество чисел) плюс некоторое количество обязательных операторов).
Давайте посчитаем количество выполненных операций в частном случае. Итак, пусть необходимо вывести все натуральные простые числа до числа 5. Очевидно, что проверка числа 1 пройдет в 1 + 2 шага, числа 2 – в 2 + 2 шага, числа 3 – в 3 + 2 шага и т. д. (прибавленная двойка к каждому числу – два обязательных оператора вне внутреннего цикла), так как мы проверяем делители во всем отрезке от 1 до проверяемого числа. В итоге количество проведенных операций (выполненных операторов на низшем уровне) представляет собой сумму: 3 + 4 + 5 + 6 + 7 (также опущен обязательный оператор ввода вне главного (внешнего) цикла). Очевидно, что при выводе всех простых чисел от 1 до n приведенная ранее сумма будет такой:
\[1 + 3 + 5 + 6 + ... + (n – 1) + n + (n + 1) + (n + 2), \]
где вместо многоточия нужно дописать все недостающие члены суммы. Очевидно, что это сумма первых (n + 2) членов арифметической прогрессии с вычтенным из нее числом 2.
Как известно, сумма k первых членов арифметической прогрессии выражена формулой:
\[S_k = \tfrac{a_1 + a_k}{2}k\]
где a1 – первый член прогрессии, ak – последний.
Подставляя в эту формулу наши исходные данные и учитывая недостающее до полной суммы число 2, получаем следующее выражение:
\[S_n = \tfrac{1+(n+2)}{2}(n+2)-2=\tfrac{(n+2)+(n+2)^2}{2}-\tfrac{4}{2}=\tfrac{n+2+n^2+4n+4-4}{2}=\tfrac{1}{2}n^2+\tfrac{5}{2}n+1\]
Чтобы найти асимптотическую сложность алгоритма, отбросим коэффициенты при переменных и слагаемые с низшими степенями (оставив, соответственно, слагаемое с самой высокой степенью). При этом у нас остается член n2, значит, асимптотическая сложность алгоритма – O(n2).
Конечно, в дальнейшем мы не будем так подробно находить асимптотическую сложность алгоритмов, а тем более, вычислять количество требуемых операций, что интересно только теоретически. На самом деле, конечно, нас интересует лишь порядок роста времени работы алгоритма (количества необходимых операций), который можно выявить из анализа вложенности циклов и некоторых других характеристик.
