Старт в науке. Решето эратосфена - алгоритм определения простых чисел

05.05.2019

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

Энциклопедичный 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 Пусть A - булевый массив, индексируемый числами от 2 до n , изначально заполненный значениями true . для i := 2, 3, 4, ..., пока i 2 ≤ n : если A [i ] = true : для j := i 2 , i 2 + i , i 2 + 2i , ..., пока j ≤ n : A [j ] := false Выход : числа i , для которых A [i ] = true .

Пример для 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 ) . Может быть представлен символически в парадигме потоков данных как

primes = [2 ..] \ [[p *p , p *p +p ..] for p in primes ]

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

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

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

Псевдокод

Вход : натуральное число n Пусть pr - целочисленный массив, поначалу пустой; lp - целочисленный массив, индексируемый от 2 до n , заполненный нулями для i := 2, 3, 4, ..., до n : если lp [i ] = 0 : lp [i ] := i pr += {i } для p из pr пока p ≤ lp [i ] и p*i ≤ n : lp [p*i ] := p Выход : все числа в массиве pr .

Решето Эратосфена - это старейший из известных способов выписывания простых чисел. В отличие от методов, обсуждавшихся в предыдущих параграфах, он не использует никакой специальной функции. Эратосфен (Erathostenes) был греческим математиком, родившимся около 284 года до н. э. Он владел многими отраслями знаний, однако современники не считали его выдающимся специалистом ни в одной из них. Они прозвали его «Бета» (вторая буква греческого алфавита) и «Пентатлосом». Вот уже 2300 лет мы пользуемся его работами, а полученные им прозвища являются лишним подтверждением величия древнегреческой математики.

«Метод для получения этих [простых чисел] называется по Эратосфену решетом, так как мы берем все нечетные числа, смешанные беспорядочно вместе, и выбрасывая из них, как неким инструментом, или решетом, мы отделяем в первую очередь неразложимые, а во вторую составные посредством их самих.»

Для дальнейшего знакомства с высказыванием Никомаха о решете смотри .

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

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

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

Теперь мы начинаем просеивать список. Первое число в нем 3. Начиная со следующего числа в списке (это 5), мы вычеркиваем из него каждое третье число. Проделав это до конца, мы вычеркнем все числа из списка, кратные 3 и большие самой тройки.

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

Например, для список нечетных чисел выглядит так:

Вычеркнув каждое третье число начиная с 5, мы получим

Теперь мы вычеркиваем каждое пятое число, начиная с 7, что дает

Мы должны бы теперь вычеркнуть каждое седьмое число, начиная с 9. Но если мы это сделаем, то никакие новые числа

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

В разобранном примере есть пара важных обстоятельств, которые нужно взять на заметку. Во-первых, хотя нам следовало повторять процесс вычеркивания вплоть до граничного числа (41 в нашем примере), мы избавились от всех составных чисел к тому моменту, когда отсеяли кратные 5, и все остальные просеивания оказались излишними. Во-вторых, некоторые числа вычеркивались больше, чем один раз. Такое произошло, например, с 15. Первый раз оно было вычеркнуто, когда мы отсеивали кратные 3. Но 15 также делится на 5, поэтому оно было вычеркнуто снова при отсеивании кратных 5.

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

Предположим, что мы отсеиваем числа, кратные какому-то простому Учитывая наше описание решета, нам следовало бы вычеркивать каждое число, начиная с следующего за числа в списке. Простейшее усовершенствование - это начинать процесс вычеркивания не с а с наименьшего числа, кратного которое не делится на простое число, меньшее Найдем его. Положительные числа, кратные записываются в виде где k - натуральное. Если то делится на число, меньшее а именно на к. Значит, первое

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

Что касается другого замечания, можем ли мы закончить отсев раньше, чем дойдем до шага? На этот раз ответ положителен, он следует того, что мы только что сделали. Допустим, например, что мы вычеркиваем каждое число. Как мы только что видели, первое число, подлежащее вычеркиванию, равно Но если такого числа нет в списке и мы можем забыть о нем. В итоге, нам нужно вычеркивать каждое до тех пор, пока Поскольку целое, это равносильно тому, что В примере, разобранном выше, Вот почему отбрасывание кратных 3 и 5 было достаточно для вылавливания всех составных чисел из списка.

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

величина ячейки, отмеченной стрелкой, равна а ее индекс - двум, поскольку она стоит на втором месте в векторе.

Вернемся к решету Эратосфена. Предположим, что мы хотим найти все простые числа, не превосходящие нечетного целого Сначала мы должны построить вектор с ячейками, по одной для каждого нечетного целого Ячейки будут принимать одно из двух возможных значений: 1 или 0. Если значение ячейки равно 0, то нечетное число, ею

представленное, было вычеркнуто на каком-то предыдущем шаге процесса просеивания. Итак, начальное значение каждой ячейки равно 1, поскольку еще нет никаких вычеркнутых чисел. Чтобы «вычеркнуть» число нужно заменить 1, стоящую в ячейке вектора, на 0. Конечно, эта ячейка могла быть «вычеркнута» на предыдущем шаге решета. В этом случае ее значение уже равно 0 и не будет меняться в процессе выполнения следующих шагов алгоритма.

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

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

Ввод: нечетное натуральное

Вывод: список всех нечетных положительных простых чисел, меньших или равных

Шаг 1. Начинаем с создания вектора ячейками, каждой из которых присвоено значение 1, и полагаем

Шаг 2. Если выписываем все числа для которых значение ячейки вектора равно 1 и останавливаемся; в противном случае переходим к шагу 3.

Шаг 3. Если значение ячейки вектора с номером равно 0, увеличиваем на 2 и возвращаемся к шагу 2; в противном случае переходим к шагу 4.

Решето Эратосфена – один из древнейших алгоритмов, позволяющих найти числа, которые называют “простыми”. Т.е. числа, которые могут делиться без остатка только на единицу и на себя. Например число 2. На что из натуральных (целых) чисел можно разделить 2, чтоб не получать остаток? Только на 2 и на 1. Или число 7. То же самое. Без остатка оно делится опять таки только на себя и единицу.

Достаточно простой алгоритм еще до нашей эры придумал хитрый дядько Эратосфен Киренский. Грек по национальности. Математик, астроном, географ. Решето дядьки Эратосфена достаточно популярный алгоритм поиска.

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

Он вычеркивает следующие числа после простого, которые от этого простого находятся на определенном расстоянии. Расстояние это рассчитывается по формуле: Текущий элемент в квадрате + значение этого элемента .

Например если число 5 простое, то следующее после него, которое стоит вычеркнуть будет равно 5*5 = 10, потом 5*5+5 = 15,потом 5*5+5+5 = 20… и так далее. Вычеркиваются таким образом числа кратные этому найденному простому. Нахождение простого начинается с числа 2. Соответственно вычеркиваются 2*2, 2*2+2, 2*2+2+2…

Хорошая иллюстрация есть на сайте Википедии:

Берем первое простое число 2 (синий кружочек) и вычеркиваем все числа, которые кратны двум (синие крестики). Потом берем простое число 3 (зеленый кружочек) и вычеркиваем все что ему кратно (зеленые крестики) и т.д.

После того, как числа вычеркнуты из списка легко определить следующее простое число – оно будет первое не вычеркнутое после текущего.

Поскольку сам код не очень то и большой, я не буду разбивать его на блоки, там нечего то и конкретизировать. Выглядит он к примеру так:

Алгоритм поиска: Решето Эратосфена

#include using namespace std; int main() { int n = 100; //Считать числа до этого //Запрашиваем массив int *a = new int; //Наполняем его числами для решета for (int i = 0; i <= n; i++) a[i] = i; //*********************************************************** //Проводим главный цикл. - Начало работы решета for (int i = 2; i * i <= n; i++) { if (a[i]) //Если текущее число не равно 0 - начинаем от него искать сложные for (int j = i*i; j <= n; j += i) //И обнуляем их ячейки, чтобы больше не проверять их в цикле a[j] = 0; } // Решето окончило отсев - в массиве остались только простые //************************************************************ //Выводим необнуленные - простые for (int i = 2; i < n; i++) { if (a[i]) { cout << a[i] << " "; } } cout << endl << endl; delete a; //И освобождаем массив return 0; }

#include

using namespace std ;

int main ()

int n = 100 ; //Считать числа до этого

//Запрашиваем массив

int * a = new int [ n + 1 ] ;

//Наполняем его числами для решета

for (int i = 0 ; i <= n ; i ++ )

a [ i ] = i ;

//***********************************************************

//Проводим главный цикл. - Начало работы решета

for (int i = 2 ; i * i <= n ; i ++ )

if (a [ i ] )

//Если текущее число не равно 0 - начинаем от него искать сложные

for (int j = i * i ; j <= n ; j += i )

//И обнуляем их ячейки, чтобы больше не проверять их в цикле

a [ j ] = 0 ;

// Решето окончило отсев - в массиве остались только простые

//************************************************************

//Выводим необнуленные - простые

for (int i = 2 ; i < n ; i ++ )

if (a [ i ] )

cout << a [ i ] << " " ;

cout << endl << endl ;

true , false ), и простыми числами считать номера элементов, которые после просеивания будут содержать true , но я решил, что это не так наглядно.

После того, как числа в массиве размещены (1,2,3,4,5,6,7,8,9,10…n) можно приступать к их просеиванию. Пока что на начальном этапе все числа в решете считаются программой простыми. Первая итерация цикла берет первое (а точнее второе по счету) число – 2. От этого числа второй цикл обнуляет элементы массива, которые попадают под фильтр-условие Число*Число+Число .

Таким образом просеиваются числа кратные двум после двойки. Далее первый цикл продолжает проход, проверяя условие if (a [ i ] ) , т.е. есть ли в ячейке число, отличающееся от нуля (мы ведь обнуляем сложные числа). Как только такое число будет найдено, опять уже от него сработает второй цикл, обнуляя после найденного кратные ему числа, стоящие после него.

И так циклы просеивают числа пока не достигнут заданной нами границы просеивания – до какого числа вылавливать простые.

Где используются простые числа? Хм… Например в криптографии. Так же в некоторых генераторах случайных чисел . Ну и конечно же в ВУЗах:) По сути решетом преподаватели тоже не гнушаются и регулярно умело балуют студентов заданиями “Нахождения простого числа”. Вот с помощью такого решета эта задача вполне решаема.

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

4.8 (96.67%) 6 votes

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

Биография ученого

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

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

Достижения

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

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

История названия и подробности нахождения

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

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

Что представляет собой алгоритм?

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

Такой вариант долгое время считался единственно эффективным, а с появлением информатики специалисты смогли делать вычисления более сложных последовательностей. При этом даже с новыми технологиями решето Эратосфена является важнейшей математической теорией.

Языки программирования в сфере арифметических расчетов

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

Использование на современных Олимпиадах по информатике

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

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

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

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

Вспомним, что простым числом , является число, которое без остатка может делиться только само на себя, ну и, конечно же, на единицу. Из школьного курса вы, наверное, помните некоторые из простых чисел - это 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. Итог работы:

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

//Алгоритм поиска простых чисел - Решето Эратосфена #include //прототип функции 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.

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