Цель работы: изучить алгоритм построения «решета Эратосфена». Задачи: 1. Изучить имеющуюся литературу по теме проекта. 2 .Провести опрос учащихся по теме. 3. Составить алгоритм нахождения простых чисел. Гипотеза: указать самое большое простое число невозможно. Методы исследования: изучение и анализ литературы по теме; наблюдение; эксперимент; анкетирование учеников школы.

Анкетирование

РЕШЕТО - Это утварь для просеивания муки, состоящая из широкого обруча и на него с одной стороны сетки. Решето отличается от сита более крупным размером отверстий сетки. Черпать воду решетом (погов.). Толковый словарь Ушакова Простые числа – это числа, которые не имеют других делителей кроме 1 и самого себя. Составные числ а – это те числа, у которых есть делители, отличные от 1 и самого себя.

Простые числа Со времён древних греков простые числа оказывались столь же привлекательными, сколь и неуловимыми. Математики постоянно испытывали разные способы их «поимки», но до сих пор единственным по-настоящему эффективным остаётся тот способ, который найден александрийским математиком и астрономом Эратосфеном. А этому методу уже около 2 тыс. лет! Этим же вопросом занимался и древнегреческий математик Эвклид.

Греческий математик Эратосфен Киренский(276г.до н.э-194г. до н.э) Эратосфен родился в Африке, в Кирене. Учился сначала в Александрии, а затем в Афинах. Вероятно, именно благодаря столь широкому образованию и разнообразию интересов Эратосфен получил от Птолемея III Эвергета приглашение вернуться в Александрию, чтобы стать воспитателем наследника престола и возглавить Александрийскую библиотеку. Эратосфен принял это предложение и занимал должность библиотекаря вплоть до своей кончины. Его научные таланты удостоились высокой оценки современника Эратосфена, Архимеда, который посвятил ему свою книгу Эфодик (т.е. метод).

Из истории математики 2, 3, 5, 7,… Для отыскания простых чисел древнегреческий математик Эратосфен придумал такой способ: он записывал все числа от 1 до какого-нибудь числа, а потом вычёркивал 1, как непростое и несоставное число. Затем вычеркивал через одно все числа идущие после 2(т.е числа кратные 2). Первым оставшимся числом после 2 стоит 3. Далее вычеркивались через два все числа, идущие после 3 (т.е числа кратные 3). Следующее, оставшееся число 5. Далее вычеркивалось каждое пятое число после 5 (т.е кратное 5). И так далее. В результате остались не вычеркнутыми только простые числа. Метод Эратосфена называют решетом Эратосфена.

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

Алгоритм 1.Из ряда чисел:2,3,4,5,6,7,8,9,10,11,12,13,14 и т. д вычёркиваем числа кратные2. 2.Теперь, кратные 3. 3.Кратные 4. 4.Кратные 5. 5.Кратные 6. 6.Делим, пока все составные числа не будут «просеяны», и останутся только простые числа: 2, 5, 7, 11, 13.... Целые положительные числа, отличные от единицы, которые без остатка делятся только на единицу и на самих себя, называются простыми. Первым из таких чисел является 2. Все остальные четные числа уже не будут простыми, так как допускают деление без остатка на 2. Нетрудно указать и еще несколько простых чисел: 3, 5, 7, 11, 13… Древнегреческий ученый Эратосфен (III - II вв. до н. э.) предложил способ, который можно описать в виде следующего алгоритма.

П ример Запишем натуральные числа, начиная от 2 до 20 в ряд. 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Первое число в списке 2 - простое. Пройдём по ряду чисел, вычёркивая все числа кратные 2 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Следующее не вычеркнутое число 3 - простое. Пройдём по ряду чисел, вычёркивая все числа кратные 3 2 3 5 6 7 9 11 12 13 15 17 19 … Процесс окончен. Все не зачеркнутые числа последовательности являются простыми.

Вывод Работая над проектом, разобралась, что такое определитель простых чисел («РЕШЕТО Эратосфена»), по его принципу создали свои таблицы и нашли простые числа от 1 до 200, показала, что в одних рядах простых чисел больше, в других – меньше, то есть встречаются они неравномерно. Но чем дальше мы продвигаемся по числовому ряду, тем реже встречаются простые числа. Возникает вопрос: а существует ли самое последнее простое число? Древнегреческий математик Евклид (ӀӀӀ в. до н.э.) в своей книге «Начала», бывшей на протяжении двух тысяч лет основным учебником математики, доказал, что простых чисел бесконечно много, то есть за каждым простым числом есть ещё большее простое число. Моя гипотеза оказалась верна, указать самое большое простое число невозможно.

Практическая значимость проекта

«Числа правят миром!» Есть числа разные на свете, Про это каждый точно знает! Число делителей, заметьте, В них тоже разное бывает. Если делится число лишь на себя и на один, То, без сомнения друзья мы назовем его простым. А если есть еще делитель, А может два иль даже три. То составным его зовите, Тут в книгу даже не смотри! Нам числа разные нужны! И числа всякие важны!

Информационные источники Толковый словарь Ушакова Александрова Эм., Лёвшин В. Стол находок утерянных чисел: Научно-художественная книга. – М.: Дет. лит., 1983. Берман Г.Н. Число и наука о нём. – М., 1960. Интернет-ресурсы.

27 сентября 2016 в 23:27

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

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

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

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

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

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

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

После выполнения этой операции незачёркнутыми в списке остаются только простые числа.

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

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

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

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

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

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

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

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

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

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

По количеству операций на бит решётка Эратосфена относительно эффективна. Оно растёт пропорционально размеру интервала от 1 до N. А вот если посмотреть, что нужно хранить в памяти для каждого шага алгоритма на больших интервалах, то ни о какой эффективности не идёт и речи.

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

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

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

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

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

На основе метода Харди-Литтлвуда учёный разработал подход, который позволяет вместо объёма оперативной памяти N использовать объём памяти ∛N (кубический корень из N).

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

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

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

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

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