[МУЗЫКА] Рассмотрим задачу. Это классическая задача с применением типа множества. Алгоритм называется «Решето Эратосфена». Я надеюсь, что на математике вы проходили этот алгоритм, но на всякий случай я вам его напомню. Диапазон от 2 до n в нашем случае будет диапазоном от 2 до 255, чтобы мы могли использовать тип множество. Итак, начнем с определения. По определению простое число имеет только два делителя — 1 и само это число. Например, 2 и 13 — это простые числа. 125 и 1 — нет. У вас возник законный вопрос, почему 1 не является простым числом? По определению. Делителя должно быть два, а у 1 — только один, поэтому 1 не считается простым числом. Итак, перейдем к методу. Мы рассмотрим два множества. Первое множество называется ALL и включает в себя все числа в диапазоне от 2 до m. И множество Prime, которое будет содержать простые числа, изначально оно пустое. Метод состоит в следующем. На первом шаге мы выбираем самое маленькое число из первого множества и помещаем его во второе. На первом шаге это будет двойка. Затем мы на втором шаге вычеркиваем из первого множества само это число, а также все числа, которые ему кратны. На первом же шаге у нас половина чисел вычеркнута. Это все четные числа, потому что они имеют делитель, равный двум. Далее мы с вами продолжаем процесс до тех пор, пока первое множество не станет пустым. При этом во втором множестве будут наши искомые простые числа. Итак, следующее значение у нас равно 3, исчезнет 3 и всё то, что ей кратно. То есть в частности исчезнет 15 и 9, и также n, которое равно 255. Следующее значение, которое попадет в множество простых чисел, это 5. Будет вычеркнута она и всё то, что кратно 5, но еще не вычеркнуто. Далее будет рассмотрено число 7, и произойдет вычеркивание. Затем число 11, которое также является простым, снова произойдет вычеркивание. 13 — и так далее. В конце концов мы с вами получим первое множество пустое, мы постепенно вычеркнем из него все значения, а множество Prime будет содержать простые числа. Теперь рассмотрим программу, которая решает эту задачу. Константа n равна 255. Дальше я рассматриваю type ent, в котором находятся числа от 2 до n. И рассматриваю две переменных типа, которые являются множествами из чисел в диапазоне от 2 до n: prime и all. nom будет иметь тип ent, это будет очередное число. И счетчик цикла будет целого типа. Первым делом множество prime делаю пустым, а в множество all помещаю все числа в диапазоне от 2 до n. Далее nom присваивается двойке — это первое самое маленькое число. Вначале я должна определить, какое самое маленькое число еще не вычеркнуто из множества. На первом шаге этот цикл, который определяет самое маленькое число, действовать не будет. А на всех остальных шагах мы будем поступать так. Пока не верно, что nom входит в множество all, мы будем увеличивать значение nom, то есть мы найдем самое маленькое число, которое является элементом, входящим в это множество. Дальше я это число добавляю в множество prime, я использую операцию объединения множеств. prime присваивается prime + множество, состоящее из одного элемента nom, теперь это число попало в множество простых. Дальше я должна вычеркнуть из множества это число и все числа, которые ему кратны. i присваиваю nom, и пока i меньше или равно n, я проделываю следующие действия. Я из множества all вычеркиваю очередное значение i, на первом шаге это будет nom, а затем к i добавляю nom, то есть получаю следующее число, которое кратно nom. И процесс продолжается до тех пор, пока я не дойду до самого большого числа в множестве. И внешний цикл завершится тогда, когда множество all станет пустым. Итак, мы с вами получили множество, содержащее простые числа. Но тут возникает законный вопрос — а как мы можем вывести значения, которые находятся в множестве? Ведь множество — это же не массив, там нет никакой упорядоченности. Мы поступаем следующим образом. Выводим сообщение «Простые числа», рассматриваем все числа в диапазоне от 2 до n, а дальше используем операцию in. Мы с вами будем выводить только те числа, которые входят в множество простых. То есть если i входит в множество prime, то мы его печатаем, используя формат 5, и для большей наглядности через каждые 50 шагов я перехожу на следующую строку. На этом цикл по выводу значений завершается, и программа заканчивается. Рассмотрим работу программы «Решето Эратосфена», которая вычисляет все простые числа. Константа n, равная 255, — это максимальное число, которое мы сможем обработать при помощи нашего алгоритма. То есть диапазон чисел, которые мы рассматриваем, не может включать более, чем 255 элементов. У нас есть два множества — prime и all, первое из них изначально пусто, а второе содержит все числа в диапазоне от 2 до n. Переменная nom показывает, какое число мы сейчас будем перемещать из множества всех чисел в множество простых. Цикл с постусловием, собственно, решает задачу. Он будет продолжаться до тех пор, пока множество all не станет пустым. Далее вложенный цикл пока ищет самое маленькое число, входящее в наше множество. На первом шаге этот цикл не будет выполняться, потому что значение nom уже известно. Далее мы помещаем это число в множество prime, то есть используем операцию объединения множеств. Далее i присваиваем nom, чтобы вычеркнуть из исходного множества все числа, которые кратны нашему числу, включая само это число. И пока i меньше или равно n, мы из множества all исключаем очередное i, и увеличиваем значение i на величину nom. Далее мы выведем простые числа. При помощи цикла по переменной i от 2 до n мы будем выводить только те числа, которые входят в множество prime. Для наглядности после каждых 50 чисел будет происходить переход на другую строку экрана. Запустим нашу программу и посмотрим, какие результаты у нас получились. Мы видим, что простые числа выведены на экран, и после каждых 50 чисел у нас начинается новая строка экрана. Можно также заметить, что чем дальше от начала числовой оси, тем в каждой полусотне чисел все меньше и меньше. То есть простые числа — это довольно редкие числа. То есть мы с вами видим, что программа работает правильно, и для решения этой задачи мы использовали тип множество. Замечу, что это классическая задача на использование множеств. [МУЗЫКА] [МУЗЫКА] [МУЗЫКА]
