Алгоритм «Решето Эратосфена» — это алгоритм определения простых чисел, разработанный древнегреческим математиком Эратосфеном Киренским, который позволяет найти все простые числа, вплоть до заданного некоего целого числа N.
Решето Эратосфена
Решетом Эратосфена называют алгоритм, который позволяет найти все простые числа вплоть до конечного натурального числа методом определения и отсева составного числа. Если говорить образно, то решето Эратосфена при тряске пропускает через себя только составные числа, простые числа не проходят через сетку решета и лежат там. Для понимания действия этого алгоритма, следует вспомнить, что такое простые числа. А это числа, которые возможно разделить лишь на единицу или на само это число. Первым простым числом будет двойка, а вторым тройка. Далее логика будет такая:
- Любое чётное число, исключая число два, являются составными. То есть они не простые, поскольку их возможно разделить помимо единицы и себя ещё и на два.
- Любые числа, которые кратны трём, исключая число три, являются составными, поскольку их можно разделить помимо единицы и себя ещё и на три.
- Четвёрка сразу отсеивается, поскольку её можно разделить просто на два.
- Пятёрка является простым числом, поскольку нет чисел, которые стоят до неё и являются её делителем.
- Если число нельзя разделить на любое простое число, стоящее до него, то это означает, что его нельзя разделить и ни на любое сложное число, которое стоит до него.
В последнем пункте задействовано правило, что любое сложное число может быть представлено в виде произведения простых чисел. Это означает, что если одно сложное число можно разделить на друге сложное число, следовательно, первое число возможно разделить на все делители второго. К примеру, двенадцать можно разделить на шесть, у которого есть делители двойка и тройка. И число двенадцать имеет в делителях и двойку и тройку.
Суть алгоритма
Суть алгоритма Эратосфена и состоит в последовательном анализе возможности деления числа на стоящие до него простые числа. Вначале находится самое первое из простых чисел в ряду натуральных и производится отсев всех кратных ему чисел. Далее надо взять очередное простое число и выполнить отсев всех кратных ему и далее таким же образом.
Если необходимо выполнить алгоритм Эратосфена программными средствами, то следует учитывать некоторые особенности. Предположим, что все натуральные числа, вплоть до последнего числа N организованы в массив. Затем по мере реализации алгоритма следует присвоить всем сложным числам, которые были обнаружены, нулевые значения. В итоге, по завершению работы алгоритма, в ячейках массива, не содержащих нулей, будут искомые простые числа, которые при необходимости можно отобразить на экране. Но массив индексируется с нуля, а ряд простых чисел начинается с числа два. Естественно, эту проблему можно решить, но она усложняет программу. Учитывая, что алгоритм Эратосфена и так довольно сложный, то получается проще пренебречь началом отсчёта чисел и организовать массив от нуля до N. Тут более важна индексация, чем значения компонентов. В качестве значений могут выступать Тruе, которым в нашем случае обозначается простое число, и Fаlsе, которое обозначит сложное число. Ниже приведён алгоритм Эратосфена. Здесь массив состоит из чисел от нуля до n включительно таким образом, что индексация компонентов будет совпадать с их величиной. А затем все сложные числа замещаются нулевыми значениями.
Рисунок 1. Алгоритм Решето Эратосфена. Автор24 — интернет-биржа студенческих работ
