Теорема.

Простых чисел бесконечно много.

Доказательство.

Предположим, что это не так. То есть, предположим, что простых чисел всего n штук, и эти простые числа есть p 1 , p 2 , …, p n . Покажем, что мы всегда можем найти простое число, отличное от указанных.

Рассмотрим число, p равное p 1 ·p 2 ·…·p n +1 . Понятно, что это число отлично от каждого из простых чисел p 1 , p 2 , …, p n . Если число p - простое, то теорема доказана. Если же это число составное, то в силу предыдущей теоремы существует простой делитель этого числа (обозначим его p n+1 ). Покажем, что этот делитель не совпадает ни с одним из чисел p 1 , p 2 , …, p n .

Если бы это было не так, то по свойствам делимости произведение p 1 ·p 2 ·…·p n делилось бы на p n+1 . Но на p n+1 делится и число p , равное сумме p 1 ·p 2 ·…·p n +1 . Отсюда следует, что на p n+1 должно делиться второе слагаемое этой суммы, которое равно единице, а это невозможно.

Так доказано, что всегда может быть найдено новое простое число, не заключающееся среди любого количества наперед заданных простых чисел. Следовательно, простых чисел бесконечно много.

Итак, в силу того, что простых чисел бесконечно много, при составлении таблиц простых чисел всегда ограничивают себя сверху каким-либо числом, обычно, 100 , 1 000 , 10 000 и т.д.

Решето Эратосфена

Сейчас мы обсудим способы составления таблиц простых чисел. Предположим, что нам нужно составить таблицу простых чисел до 100 .

Самым очевидным методом решения этой задачи является последовательная проверка целых положительных чисел, начиная с 2 , и заканчивая 100 , на наличие положительного делителя, который больше 1 и меньше проверяемого числа (из свойств делимости мы знаем, что абсолютная величина делителя не превосходит абсолютной величины делимого, отличного от нуля). Если такой делитель не найден, то проверяемое число является простым, и оно заносится в таблицу простых чисел. Если же такой делитель найден, то проверяемое число является составным, оно НЕ заносится в таблицу простых чисел. После этого происходит переход к следующему числу, которое аналогично проверяется на наличие делителя.

Опишем несколько первых шагов.

Начинаем с числа 2 . Число 2 не имеет положительных делителей, кроме 1 и 2 . Следовательно, оно простое, поэтому, заносим его в таблицу простых чисел. Здесь следует сказать, что 2 является наименьшим простым числом. Переходим к числу 3 . Его возможным положительным делителем, отличным от 1 и 3 , является число 2 . Но 3 на 2 не делится, поэтому, 3 – простое число, и его также нужно занести в таблицу простых чисел. Переходим к числу 4 . Его положительными делителями, отличными от 1 и 4 , могут быть числа 2 и 3 , проверим их. Число 4 делится на 2 , поэтому, 4 – составное число, и его не нужно заносить в таблицу простых чисел. Обратим внимание на то, что 4 – наименьшее составное число. Переходим к числу 5 . Проверяем, являются ли его делителем хотя бы одно из чисел 2 , 3 , 4 . Так как 5 не делится ни на 2 , ни на 3 , ни на 4 , то оно простое, и его надо записать в таблицу простых чисел. Дальше происходит переход к числам 6 , 7 , и так далее до 100 .

Такой подход к составлению таблицы простых чисел является далеко не идеальным. Так или иначе, он имеет право на существование. Отметим, что при этом способе построения таблицы целых чисел можно использовать признаки делимости , которые немного ускорят процесс поиска делителей.

Существует более удобный способ для составления таблицы простых чисел, называемый . Присутствующее в названии слово «решето» не случайно, так как действия этого метода помогают как бы «просеять» сквозь решето Эратосфена целые числа, большие единицы, чтобы отделить простые от составных.

Покажем решето Эратосфена в действии при составлении таблицы простых чисел до 50 .

Сначала записываем по порядку числа 2, 3, 4, …, 50 .

Первое записанное число 2 является простым. Теперь от числа 2 последовательно перемещаемся вправо на два числа и зачеркиваем эти числа, пока не доберемся до конца составляемой таблицы чисел. Так будут вычеркнуты все числа, кратные двум.

Первым следующим за 2 невычеркнутым числом является 3 . Это число простое. Теперь от числа 3 последовательно перемещаемся вправо на три числа (учитывая и уже зачеркнутые числа) и вычеркиваем их. Так будут вычеркнуты все числа, кратные трем.

Первым следующим за 3 невычеркнутым числом является 5 . Это число простое. Теперь от числа 5 последовательно перемещаемся вправо на 5 чисел (учитываем и зачеркнутые ранее числа) и вычеркиваем их. Так будут вычеркнуты все числа, кратные пяти.

Дальше вычеркиваем числа, кратные 7 , затем, кратные 11 и так далее. Процесс заканчивается, когда не останется чисел для вычеркивания. Ниже показана законченная таблица простых чисел до 50 , полученная с помощью решета Эратосфена. Все незачеркнутые числа являются простыми, а все зачеркнутые числа – составными.

Давайте еще сформулируем и докажем теорему, которая позволит ускорить процесс составления таблицы простых чисел при помощи решета Эратосфена.

Теорема.

Наименьший положительный и отличный от единицы делитель составного числа a не превосходит , где - из a .

Доказательство.

Обозначим буквой b наименьший и отличный от единицы делитель составного числа a (число b является простым, что следует из теоремы, доказанной в самом начале предыдущего пункта). Тогда существует такое целое число q , что a=b·q (здесь q – положительное целое число, что следует из правил умножения целых чисел), причем (при b>q нарушится условие, что b – наименьший делитель числа a , так как q также является делителем числа a в силу равенства a=q·b ). Умножив обе части неравенства на положительное и большее единицы целое число b (это нам позволяют сделать ), получаем , откуда и .

Что же нам дает доказанная теорема, касательно решета Эратосфена?

Во-первых, вычеркивание составных чисел, кратных простому числу b следует начинать с числа, равного (это следует из неравенства ). Например, вычеркивание чисел, кратных двум, следует начинать с числа 4 , кратных трем – с числа 9 , кратных пяти – с числа 25 , и так далее.

Во-вторых, составление таблицы простых чисел до числа n с помощью решета Эратосфена можно считать законченным тогда, когда будут вычеркнуты все составные числа, кратные простым числам, не превосходящим . В нашем примере n=50 (так как мы составляем таблицу простых чисел до 50 ) и , поэтому решето Эратосфена должно отсеять все составные числа, кратные простым числам 2 , 3 , 5 и 7 , которые не превосходят арифметического квадратного корня из 50 . То есть, нам дальше не нужно заниматься поиском и вычеркиванием чисел, кратных простым числам 11 , 13 , 17 , 19 , 23 и так далее до 47 , так как они уже будут вычеркнуты, как кратные меньшим простым числам 2 , 3 , 5 и 7 .

Данное число простое или составное?

Некоторые задания требуют выяснения, является ли данное число простым или составным. В общем случае эта задача далеко не проста, особенно для чисел, запись которых состоит из значительного количества знаков. В большинстве случаев приходится искать какой-либо специфический способ ее решения. Однако мы попробуем дать направление ходу мыслей для несложных случаев.

Несомненно, можно попробовать воспользоваться признаками делимости для доказательства того, что данное число является составным. Если, к примеру, некоторый признак делимости показывает, что данное число делится на некоторое целое положительное число большее единицы, то исходное число является составным.

Пример.

Докажите, что число 898 989 898 989 898 989 составное.

Решение.

Сумма цифр данного числа равна 9·8+9·9=9·17 . Так как число, равное 9·17 делится на 9 , то по признаку делимости на 9 можно утверждать, что исходное число также делится на 9 . Следовательно, оно составное.

Существенный недостаток такого подхода заключается в том, что признаки делимости не позволяют доказать простоту числа. Поэтому при проверке числа на то, является ли оно простым или составным, нужно действовать иначе.

Самый логичный подход состоит в переборе всех возможных делителей данного числа. Если ни один из возможных делителей не будет истинным делителем данного числа, то это число будет простым, в противном случае – составным. Из теорем, доказанных в предыдущем пункте, следует, что делители данного числа a нужно искать среди простых чисел, не превосходящих . Таким образом, данное число a можно последовательно делить на простые числа (которые удобно брать из таблицы простых чисел), пытаясь найти делитель числа a . Если будет найден делитель, то число a – составное. Если же среди простых чисел, не превосходящих , не окажется делителя числа a , то число a – простое.

Пример.

Число 11 723 простое или составное?

Решение.

Выясним, до какого простого числа могут быть делители числа 11 723 . Для этого оценим .

Достаточно очевидно, что , так как 200 2 =40 000 , а 11 723<40 000 (при необходимости смотрите статью сравнение чисел ). Таким образом, возможные простые делители числа 11 723 меньше числа 200 . Это уже значительно облегчает нашу задачу. Если бы мы этого не знали, то нам бы пришлось перебирать все простые числа не до 200 , а вплоть до числа 11 723 .

При желании можно оценить более точно. Так как 108 2 =11 664 , а 109 2 =11 881 , то 108 2 <11 723<109 2 , следовательно, . Таким образом, любое из простых чисел, меньших 109 , потенциально является простым делителем данного числа 11 723 .

Теперь мы будем последовательно делить число 11 723 на простые числа 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 . Если число 11 723 разделится нацело на одно из записанных простых чисел, то оно будет составным. Если же оно не делится ни на одно из записанных простых чисел, то исходное число простое.

Не будем описывать весь этот монотонный и однообразный процесс деления. Сразу скажем, что 11 723

Запишем натуральные числа начиная от 2 до 20 в ряд:

Первое число в списке 2 - простое. Пройдём по ряду чисел, вычёркивая все числа кратные 2 (каждое второе, начиная с 2 2 = 4 ):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Следующее невычеркнутое число 3 - простое. Пройдём по ряду чисел, вычёркивая все числа кратные 3 (каждое третье, начиная с 3 2 = 9 ):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Следующее невычеркнутое число 5 - простое. Пройдём по ряду чисел, вычёркивая все числа кратные 5 (каждое пятое, начиная с 5 2 = 25 ). И т. д.

Необходимо провести вычёркивания кратных для всех простых чисел p , для которых . В результате все составные числа будут вычеркнуты, а невычеркнутыми останутся все простые числа. Для n = 20 уже после вычёркивания кратных числу 3 все составные числа получаются вычеркнутыми.

Примеры реализации

Turbo Pascal

Prost:=1 ; //Подготовка параметра для нахождения простых чисел for i:=1 to n do //Цикл движения по массиву чисел begin //НАЧАЛО if p[ i] =0 then continue else //Чтоб лишний раз не заходить в цикл inc(prost) ; //Увеличение параметра, j:=i; //Подготовка параметра вложенного цикла while j<=n do //Вложенный цикл для определения простых чисел if (p[ j] mod prost=0 ) //Если остаток от деления элемента на следующее простое число равен 0.. and (p[ j] <>0 ) //..и этот элемент не равен 0.. and (p[ j] >prost) then //..и этот элемент больше параметра prost.. begin p[ j] :=0 ; inc(j) ; end //..это СОСТАВНОЕ число, удаляем его из массива и ищем далее else inc(j) ; //иначе это простое число, и дальнейший поиск end ; //КОНЕЦ

Wikimedia Foundation . 2010 .

Смотреть что такое "Эратосфена решето" в других словарях:

Метод в теории чисел, назван по имени Эратосфена, заключающийся в отсеивании (например, путём зачёркивания) тех целых чисел заданной последовательности а1, a2,..., aN (например, натурального ряда чисел), которые делятся хотя бы на одно из … Большая советская энциклопедия

Метод, разработанный Эратосфеном (3 в. до н. э.) и позволяющий отсеивать составные числа из натурального ряда. Сущность Э. р. заключается в следующем. Зачеркивается единица. Число 2 простое. Зачеркиваются все натуральные числа, делящиеся на 2.… … Математическая энциклопедия

В математике решето Аткина быстрый современный алгоритм нахождения всех простых чисел до заданного целого числа N. Основная идея алгоритма состоит в использовании неприводимых квадратичных форм (представление чисел в виде ax²+by²).… … Википедия

В математике решето Сундарама детерминированный алгоритм нахождения всех простых чисел до некоторого целого числа. Разработан индийским студентом С. П. Сундарамом в 1934 году. Содержание 1 Описание 2 Обоснование … Википедия

Алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену Киренскому. Содержание 1 Алгоритм … Википедия

Этим именем называют следующий способ получения ряда простых чисел. Из ряда чисел 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14... вычеркивают кратные двум; 4, 6, 8, 10, 12,... кратные трем: 6, 9, 12, 15,... кратные пяти: 10, 15, 20, 25, 30,...… … Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона

Один из решета методов в элементарной теории чисел, созданный В. Вруном ; является развитием Эратосфена решета. Метод Б. р. заключается в следующем: из последовательности натуральных чисел высеиваются (выбрасываются) числа с малыми простыми… … Математическая энциклопедия

Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и … Википедия

Служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не устанавл … Википедия

У этого термина существуют и другие значения, см. Тест Миллера. Не следует путать с «Тестом Миллера Рабина» вероятностным полиномиальным тестом простоты. Тест Миллера детерминированный полиномиальный тест простоты. В 1976 году Миллер… … Википедия

) исключаются.

Энциклопедичный YouTube

1 / 5

✪ Решето Эратосфена на Си

✪ Решето Эратосфена

✪ Решето Эратосфена

✪ Лекция 44: Решето Эратосфена

✪ Простые числа. Математика

Субтитры

История

Название «решето» метод получил потому, что, согласно легенде, Эратосфен писал числа на дощечке, покрытой воском, и прокалывал дырочки в тех местах, где были написаны составные числа . Поэтому дощечка являлась неким подобием решета, через которое «просеивались» все составные числа, а оставались только числа простые. Эратосфен дал таблицу простых чисел до 1000.

Алгоритм

Доказательство сложности

При выбранном n ∈ N {\displaystyle n\in \mathbb {N} } для каждого простого p ∈ P: p ≤ n {\displaystyle p\in \mathbb {P} \colon p\leq n} будет выполняться внутренний цикл, который совершит n p {\displaystyle {\frac {n}{p}}} действий. Следовательно, нужно оценить следующую величину:

∑ p ∈ P: p ≤ n n p = n ⋅ ∑ p ∈ P: p ≤ n 1 p {\displaystyle \sum \limits _{p\in \mathbb {P} \colon p\leq n}{\frac {n}{p}}=n\cdot \sum \limits _{p\in \mathbb {P} \colon p\leq n}{\frac {1}{p}}}

Псевдокод

Оптимизированная реализация (начинающаяся с квадратов) на псевдокоде :

Пример для n = 30

Запишем натуральные числа начиная от 2 до 30 в ряд:

Первое число в списке, 2 - простое. Пройдём по ряду чисел, зачёркивая все числа кратные 2 (то есть каждое второе, начиная с 2 2 = 4 ):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Следующее незачеркнутое число, 3 - простое. Пройдём по ряду чисел, зачёркивая все числа кратные 3 (то есть каждое третье, начиная с 3 2 = 9 ):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Следующее незачеркнутое число, 5 - простое. Пройдём по ряду чисел, зачёркивая все числа кратные 5 (то есть каждое пятое, начиная с 5 2 = 25 ). И т. д.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Следующее незачеркнутое число - 7 . Его квадрат, 49 - больше 30 -ти, поэтому на этом работа завершена. Все составные числа уже зачеркнуты:

2 3 5 7 11 13 17 19 23 29

Модификации метода

Неограниченный, постепенный вариант

В этом варианте простые числа вычисляются последовательно, без ограничения сверху, как числа находящиеся в промежутках между составными числами, которые вычисляются для каждого простого числа p , начиная с его квадрата, с шагом в p (или для нечетных простых чисел 2p ) . Может быть представлен символически в парадигме потоков данных как

Первое простое число 2 (среди возрастающих положительных целых чисел) заранее известно, поэтому в этом самореферентном определении нет порочного круга .

Перебор делителей

Решето Эратосфена часто путают с алгоритмами, которые отфильтровывают из заданного интервала составные числа , тестируя каждое из чисел-кандидатов с помощью перебора делителей .

Псевдокод

Решето Эратосфена – это алгоритм нахождения простых чисел до заданного натурального числа путем постепенного отсеивания составных чисел. Образно говоря, через решето Эратосфена в процессе его тряски проскакивают составные числа, а простые остаются в решете.

Чтобы понять данный алгоритм, вспомним, что числа являются простыми, если делятся только на единицу и самих себя. Первое простое число - это 2, второе простое число - это 3. Теперь начнем рассуждать:

1. Все четные числа, кроме двойки, - составные, т. е. не являются простыми, так как делятся не только на себя и единицу, а также еще на 2.
2. Все числа кратные трем, кроме самой тройки, - составные, так как делятся не только на самих себя и единицу, а также еще на 3.
3. Число 4 уже выбыло из игры, так как делится на 2.
4. Число 5 простое, так как его не делит ни один простой делитель, стоящий до него.
5. Если число не делится ни на одно простое число, стоящее до него, значит оно не будет делиться ни на одно сложное число, стоящее до него.

Последний пункт вытекает из того, что сложные числа всегда можно представить как произведение простых. Поэтому если одно сложное число делится на другое сложное, то первое должно делиться на делители второго. Например, 12 делится на 6, делителями которого являются 2 и 3. Число 12 делится и на 2, и на 3.

Алгоритм Эратосфена как раз заключается в последовательной проверке делимости чисел на предстоящие простые числа. Сначала берется первое простое и из ряда натуральных чисел высеиваются все кратные ему. Затем берется следующее простое и отсеиваются все кратные ему и так далее.

При реализации алгоритма Эратосфена на языке программирования есть некоторая сложность. Допустим, мы помещаем натуральные числа до заданного числа n в массив. Далее в процессе выполнения алгоритма будем заменять обнаруженные сложные числа нулями. После выполнения алгоритма те ячейки массива, которые не содержат нули, содержат простые числа, которые выводятся на экран.

Однако индексация массива начинается с нуля, а простые числа начинаются с двойки. Эта проблема решаема, но добавляет сложности в код. Поскольку алгоритм Эратосфена не такой уж простой, легче пренебречь началом и взять массив от 0 до n . Здесь важнее индексы, чем значения элементов. Значениями может быть True, обозначающее простое число, и False, обозначающее сложное число.

В данном примере реализации алгоритма Эратосфена список заполняется числами от 0 до n включительно так, что индексы элементов совпадают с их значениями. Далее все непростые числа заменяются нулями:

n = int (input () ) # список заполняется значениями от 0 до n a = for i in range (n + 1 ) : a.append (i) # Вторым элементом является единица, # которую не считают простым числом # забиваем ее нулем. a[ 1 ] = 0 # начинаем с 3-го элемента i = 2 while i <= n: # Если значение ячейки до этого не было обнулено, # в этой ячейке содержится простое число. if a[ i] != 0 : # первое кратное ему будет в два раза больше j = i + i while j <= n: # это число составное, поэтому заменяем его нулем a[ j] = 0 # переходим к следующему числу, которое кратно i (оно на i больше) j = j + i i += 1 # Превращая список во множество, # избавляемся от всех нулей кроме одного. a = set (a) # удаляем ноль a.remove (0 ) print (a)

Пример выполнения.

Переключить меню

В этот статье мы сделаем экскурс в алгоритмы поиска простых чисел и рассмотрим один из алгоритмов, который реализует такой поиск. Этот метод поиска получил название "", в честь древнегреческого математика Эратосфена Киренского. А "решето" потому, что мы как бы просеиваем массив чисел, оставляя в нем только простые числа.

Вспомним, что простым числом , является число, которое без остатка может делиться только само на себя, ну и, конечно же, на единицу. Из школьного курса вы, наверное, помните некоторые из простых чисел - это 5, 7, 11, 13, 17 и так далее. Давайте теперь рассмотрим сам принцип работы алгоритма поиска простых чисел. Этот метод поиска достаточно прост, поэтому, при желании, вам все станет очень скоро понятно.

Решето Эратосфена - алгоритм работы. Язык программирования С++

1. Для примера мы будем производить поиск простых чисел в интервале от 0 до 1000. Для этого нам нужно создать массив логических элементов размерностью 1000. Почему логических, поймете далее. Объявляем массив

Const int size = 1000; bool array;

2. Теперь нам нужно присвоить начальные значения элементам массива, т.к. на данный момент они содержат различный системный "мусор". Поступим так: присвоим всем элементам массива значения "true" - истина или единица. По мере работы алгоритма поиска простых чисел, все элементы массива (они у нас изначально установлены в true) с "простыми" индексами (заметьте, что здесь речь идет именно об индексах, т.к. наши искомые простые числа у нас будут выражаться в значениях индексов элементов массива) останутся быть равными "true", а все остальные установятся в "false" - ложь, или нуль. Т.е. теперь вы поняли, почему массив у нас содержит логические значения, а если и что-то не понятно, то, разобрав код, все встанет на свои места. Заполняем массив, начиная со второй ячейки, т.к. 0 и 1 не относят к простым, а значит и можно сразу их исключить

For(int k = 2; k < size; k++) array[k] = true;

3. А теперь самое важное: рассмотрим сам алгоритм поиска простых чисел, т.е. само решето Эратосфена

Для того чтобы просматривать массив и его индексы нам нужен цикл - делаем цикл (0 и 1 индексы мы не просматриваем). В этом цикле мы будем просматривать значения от 2 до значения корня из size. Почему так? Потому что, дойдя до корня из size, уже будут отсеяны все числа, не относящиеся простым. Поступая таким образом, мы уменьшаем количество итераций, а, соответственно, и нагрузку на процессор компьютера, что есть хорошо.

For(int i = 2; i < sqrt(size); i++) { }

Для "просева" на решете Эратосфена находится первый элемент массива с истинным значением. В самом начале работы программы этим элементом будет элемент с индексом 2. Далее выполняется условие if и мы попадаем на внутренний цикл for, который служит для просмотра остальной части массива (с 3 по 1000 индексы). Значение каждого индекса, а наши числа у нас выражены в индексах, будут проверяться на наличие остатка от деления на 2. Если число делится без остатка, значит, оно уже не может быть простым и значит, соответственно, выставляем эту ячейку в false. Смотрим код

For(int i = 2; i < sqrt(size); i++) { if(array[i] == true) { for(int j = i * 2; j < size; j++) { if(j % i == 0) array[j] = false; } } }

Для более наглядной демонстрации того, что произойдет после первой итерации, где i = 2 привожу рисунок для массива из 20 значений, по аналогии вы поймете, что происходит с нашим массивом из 1000 элементов.

Как видите, все элементы массива со значениями индексов, кратных двум "просеялись" и отметились как false. Это примерно половина значений всего нашего массива.

Переходим на следующую итерацию, в которой i = 3. Выполняется условие if, т.к. 3 не было "просеяно" в предыдущей итерации, попадаем опять же на внутренний цикл, который обрабатывает оставшуюся часть массива (индексы от 4 до 1000).

Рисунок ниже иллюстрирует полученную картину

Как видите, были исключены все числа, кратные трем, не исключенные ранее "двойкой".

Переходим к следующей итерации, где i = 4. Здесь условие if не выполняется, поэтому "просеиваться" ничего не будет. Далее, следующая итерация с i = 5, здесь будут помечены в false значения массива с индексами кратными 5, которые не были помечены ранее по иным критериям: исключаются 25, 35, 45 и так далее. Следующими "рабочими" итерациями, в которых будут выполняться "просевы" являются итерации с i = 7, 11, 13, 17 и так далее, вплоть до корня из size (т.к. после него уже не может встретиться число, не относящееся к простому).

4. Завершающим этапом работы алгоритма "Решето Эратосфена", является печать результатов. Для вывода результатов воспользуемся таким циклом

For(int i = 2; i < mySize; i++) { if(myArray[i] == true) cout << i << endl; }

5. Итог работы:

Алгоритм поиска простых чисел - решето Эратосфена на С++. Первый способ

//прототип функции void printarray(bool, const int); using namespace std; int main() { const int size = 1000; bool array; for(int k = 2; k < size; k++) array[k] = true; for(int i = 2; i < sqrt(size); i++) { if(array[i] == true) { for(int j = i * 2; j < size; j++) { if(j % i == 0) array[j] = false; } } } printarray(array, size); return 0; } //функция для вывода результатов работы void printarray(bool myArray, const int mySize) { int counter = 0; for(int i = 2; i < mySize; i++) { if(myArray[i] == true) { cout << i << endl; counter++; } } //выводим общее количество найденных простых чисел cout << endl << "Total: " << counter << endl; }

Результат работы программы: (было найдено 168 простых чисел)

6. В пятом пункте был изложен первый способ реализации алгоритма поиска простых чисел. Предлагаю вашему вниманию и второй способ, в котором массив будет содержать не логические значения (истина / ложь), а значения целых чисел, которые мы будем "просеивать" на решете Эратосфена. Т.е. принцип работы алгоритма тот же, только реализация несколько иная. Возможно, вам эта реализация понравится даже более предыдущей, смотрим код

Алгоритм поиска простых чисел - решето Эратосфена на С++. Второй способ

//Решето Эратосфена #include void simplePrint(int, const int); using namespace std; int main() { const int size = 100; int array; for(int k = 0; k < size; k++) array[k] = k; array = 0; for(int i = 2; i < sqrt(size); i++) { if(array[i] != 0) { for(int j = i * 2; j < size; j += i) { array[j] = 0; } } } simplePrint(array, size); return 0; } void simplePrint(int array, const int size) { for(int i = 0; i < size; i++) if(array[i] != 0) cout << array[i] << endl; }

В этой реализации мы также задаем массиву начальные значения, но уже не логические, а числовые (0, 1, 2, 3, 4, 5 ...). Эти числовые значения и будут теми числами, которые мы будем "просеивать" на решете Эратосфена. Задаем значения таким кодом

For(int k = 0; k < sqrt(size); k++) array[k] = k;

Числа, которые не будут являться простыми, мы будем помечать, как ноль. Мы знаем, что числа 0 и 1 не являются простыми числами, поэтому их сразу можно пометить в нули: первая ячейка массива итак нулевая, а вот вторую, содержащую единицу, нужно поменять

For(int i = 2; i < sqrt(size); i++) { if(array[i] != 0) { for(int j = i * 2; j < size; j += i) { array[j] = 0; } } }

Разберем первую итерацию: i = 2. Выполняется условие if, т.к. вторая ячейка у нас содержит значение 2, и мы переходим во внутренний цикл, который и будет "просеивать" числа. Рассмотрев код, мы видим, что меняются (помечаются) в ноль все значения массива, кратные двум (4, 6, 8, 10, 12 и так далее). В следующей итерации будет то же самое, но уже с шагом 3, помечаются в ноль значения (6, 9, 12, 15, 18 и так далее).

После окончания работы алгоритма поиска простых чисел, выводим значения элементов массива, не равных нулю на экран. Это и будут найденные простые числа

For(int i = 0; i < size; i++) if(array[i] != 0) cout << array[i] << endl;

7. При желании, можно как в первой реализации, так и во второй, собрать найденные значения простых чисел в новый массив, который мы создадим динамически. Для этого нужно немного изменить код функции, печатающей результаты работы алгоритма. Вот полученный код

//функция для вывода результатов работы void printarray(bool myArray, const int mySize) { int counter = 0; //подсчитываем количество найденных простых чисел for(int i = 2; i < mySize; i++) if(myArray[i] == true) counter++; //выводим общее количество найденных простых чисел cout << endl << "Total: " << counter << endl << endl; //динамически создаем массив нужного размера int *simple = new int; //заполняем созданный массив простыми числами for(int i = 2, k = 0; i < mySize; i++) if(myArray[i] == true) simple = i; //выводим содержимое на экран for(int i = 0; i < counter; i++) cout << simple[i] << endl; }

Объявляем счетчик counter, который будет считать количество найденных простых чисел. Затем, зная их количество, мы можем динамически создать массив и наполнить его простыми числами. В конце функции выводим его содержимое на экран, тем самым демонстрируя список найденных величин, присутствующих в интервале от 0 до 1000.

Итак, алгоритм поиска простых чисел мы рассмотрели, в частности для этого было использовано "решето Эратосфена". Все вопросы по алгоритму можно задать на форуме, либо в комментариях.