[МУЗЫКА]
Рассмотрим задачу.
Это классическая задача с применением типа множества.
Алгоритм называется «Решето Эратосфена».
Я надеюсь, что на математике вы проходили этот алгоритм,
но на всякий случай я вам его напомню.
Диапазон от 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 чисел у нас начинается новая строка экрана.
Можно также заметить, что чем дальше от начала числовой оси,
тем в каждой полусотне чисел все меньше и меньше.
То есть простые числа — это довольно редкие числа.
То есть мы с вами видим, что программа работает правильно,
и для решения этой задачи мы использовали тип множество.
Замечу, что это классическая задача на использование множеств.
[МУЗЫКА]
[МУЗЫКА]
[МУЗЫКА]
