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

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

Запишем натуральные числа начиная от 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 году Миллер… … Википедия

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

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

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

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

Достижения

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

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

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

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

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

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

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

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

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

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

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

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

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

Математик оптимизировал решето Эратосфена, чтобы искать простые числа с меньшим расходом памяти

• Научно-популярное

38-летний перуанский математик Харальд Хельфготт три года назад доказал тернарную гипотезу Гольдбаха, а сейчас сумел оптимизировать компьютерный алгоритм для расчёта решета Эратосфена. Фото: Matías Loewy

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

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

В виде алгоритма решето Эратосфена формализуется следующим образом:

1. Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
2. Пусть переменная p изначально равна двум - первому простому числу.
3. Зачеркнуть в списке числа от 2p до n считая шагами по p (это будут числа кратные p: 2p, 3p, 4p, …).
4. Найти первое незачёркнутое число в списке, большее чем p, и присвоить значению переменной p это число.
5. Повторять шаги 3 и 4, пока возможно.

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

Харальд Хельфготт

Тернарная гипотеза Гольдбаха напрямую следует из бинарной гипотезы. Тернарная гипотеза утверждает, что любое нечётное число, начиная с 7, можно представить в виде суммы трёх простых чисел. Эта гипотеза была доказана для чисел от N до бесконечности Иваном Виноградовым в 1937 году, за что он получил Сталинскую премию и звание Героя Социалистического Труда. Советские математики думали, что Виноградов доказал гипотезу для всех чисел, но на самом деле позже выяснилось, что нижняя граница N в работе Виноградова составляет 10 6 846 168 .

Перуанский математик Харальд Хельфготт сумел окончательно доказать эту гипотезу, снизив границу N до приемлемого числа 10 29 , а все остальные числа проверили на суперкомпьютере. Его доказательство опубликовано в журнале Science 24 мая 2013 года (doi: 10.1126/science.340.6135.913). Оно подтверждено другими квалифицированными математиками, способными понять доказательство, например, Теренсом Тао .

Сейчас талантливый математик Харальд Хельфготт, чьи предки происходят из Черновицкой области, направил свои усилия на ещё одну важную задачу современной науки - оптимизацию поиска простых чисел. Ему удалось предложить улучшенный вариант решётки Эратосфена - метода поиска простых чисел, сформулированного примерно в 240 г до н.э. Новый вариант в компьютерной реализации требует меньше оперативной памяти, что означает меньший объём подкачки страниц из виртуальной памяти - следовательно, процесс существенно ускоряется.

«Как и многие другие 10-летние дети, я изучал решето Эратосфена в начальной школе», - говорит Харальд Хельфготт, который сейчас работает в Национальном центре научных исследований Франции и Гёттингенском университете.

Харальд признался, что начал думать «даже слишком много» о решётке Эратосфена ещё во время работы над тернарной проблемой Гольдбаха. В частности, об объёме данных в памяти. Он понимал, что именно ограниченный объём памяти является бутылочным горлышком, которое снижает максимально возможную скорость вычислений в данном случае.

Специалисты говорят, что эффективность алгоритма определяется двумя факторами:

1. Количество операций на один бит входных данных.
2. Количество бит в памяти во время выполнения инструкций.

Оптимизация решета Эратосфена

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

Сам математик объясняет метод следующим образом:

«Анализ количества решений производится, по сути, посредством преобразования Фурье . Представьте себе, что простые числа - это звуки на некоторой записи, скажем, в моменты времени 2, 3, 5, 7, 11 и так далее микросекунд. После преобразования у вас получается своего рода шум, в котором вы пытаетесь услышать какие-то ноты. Среди них есть такие, которые слышны достаточно хорошо, - это и есть большие дуги. А есть частоты, которые просто являются шумовыми фрагментами, - это малые дуги. Весь метод распадается на две части - выделение нот и доказательство того, что остальное на самом деле шум. За первую часть метода отвечают оценки на большие дуги, за второй - на малые».

Образно говоря, вместо 1 гигабайта памяти, т.е. 10 9 байт (не путать с гибибайтом 2 30) нужен всего лишь 1 килобайт (∛10 9 = 10 3 байт).

Гигабайт и килобайт - большая разница, согласитесь.

Такая оптимизация в каком-то смысле стала побочным эффектом решения проблемы Гольдбаха.

Тезисы своей работы Харальд Хельфготт представил на