Решение задачи №4038
Условие задачи №4038:
Дано натуральное число n. Вывести на экран n первых простых чисел. Например, при вводе числа 10 программа должна вывести ответ: 2 3 5 7 11 13 17 19 23 29.Решение
Описание отсутствуетРешение:
Эта задача похожа на предыдущую тем, что здесь нам тоже необходимо проверить все натуральные числа на некотором отрезке, на этот раз используя еще один счетчик для подсчета найденных простых. Однако на этот раз мы не можем узнать, сколько придется проверить чисел, пока не насчитается n простых. Следовательно, здесь нам не подходит цикл for, так как мы не можем посчитать необходимое количество итераций.
Здесь нам поможет цикл while. Напомним, что тело цикла while повторяется до тех пор, пока остается истинным булевское выражение в его заголовке (поэтому его еще называют циклом с предусловием). Так как while не имеет переменной цикла, которая увеличивается на 1 с каждым следующим шагом, то при его использовании необходимо обеспечить изменение некоторых переменных в теле цикла, от которых зависит условие в его заголовке, таким образом, чтобы при достижении требуемого результата оно стало ложным.
Так как мы должны найти и вывести n первых простых чисел, подсчитывая их, и с каждый найденным простым числом некоторый счетчик (пусть это будет primes с начальным значением 0) увеличивается на 1, то условием в заголовке while будет выражение primes < n. Иными словами, цикл продолжается, пока число найденных чисел меньше требуемого. На последнем же шаге будет выведено последнее число, primes станет равным n и следующего шага цикла уже не будет, так как условие в его заголовке станет ложным. На этом работа программы будет закончена.
Проверяться на простоту будет некоторое число k, которое с каждой итерацией цикла обязательно будет увеличиваться на 1 (таким образом, мы будем двигаться по отрезку натуральных чисел, пока не выберем из него заданное количество простых).
Алгоритм на естественном языке:
1) Ввод n;
2) Обнуление переменной primes;
3) Присваивание переменной k значения 1;
4) Запуск цикла с предусловием primes < n. В цикле:
1. Обнуление переменной count;
2. Запуск цикла, при котором i изменяется от 1 до k. В цикле:
Если k делится на i, то увеличиваем значение переменной count на 1;
3. Если count = 2, выводим на экран число k, символ пробела и увеличиваем значение счетчика primes на 1;
4. Увеличиваем значение k на 1.
Код:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | program FirstNPrimes; var i, k, n, count, primes: word; begin readln(n); k := 1; primes := 0; while primes < 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 begin write(k, ' '); inc(primes) end; inc(k) endend. |
Выполним ручную прокрутку алгоритма, взяв в качестве n число 2. При этом будем уже по привычке красным цветом обозначать переменные, изменившиеся после выполнения данной строки, а прочерком те, которые на данном шаге не определены, так как алгоритм до них еще «не дошел». При повторении шагов цикла итерации явно считать не будем (хотя легко увидеть, что их номерам полностью соответствует изменяющаяся после каждого очередного выполнения тела переменная k), и в таблице будет указана лишь та строка, которая выполняется. На тех шагах, на которых переменные не изменяются, будем пояснять смысл выполняющихся операторов.
Для наглядности все же отделим друг от друга четные и нечетные шаги основного цикла while, при этом его внутренний цикл будем считать самоочевидным и в строке 12-14 будем фиксировать те значения переменных, которые будут получены по выходу из него.
Как видим, описать действия даже такого элементарного алгоритма и даже при столь малых исходных данных – достаточно трудоемкая и трудно проверяемая задача, поэтому очень важно понимать логику самой программы и уметь представлять себе целостную картину ее поведения с минимальными потребностями в моделировании.
Вычислительная сложность:
Так как в данной задаче в главном цикле присутствует вложенный, в котором происходит ровно k операций (сложность этой конструкции мы определили в задаче 19), то его сложность явно не меньше O(n2) и превышает ее, так как нам явно необходимо выполнить более чем n шагов главного цикла. При этом точность расчета сложности зависит от распределения простых чисел, которое описывается с помощью достаточно сложных математических приемов и утверждений, так что мы не будем далее рассматривать эту задачу.
