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

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

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

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

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-летний перуанский математик Харальд Хельфготт .

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

Харальд Хельфготт привлёк всеобщее внимание в 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. Количество операций на один бит входных данных.
2. Количество бит в памяти во время выполнения инструкций.

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

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

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

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

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

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

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

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

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

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

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

Цель работы: изучить алгоритм построения «решета Эратосфена». Задачи: 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. Интернет-ресурсы.

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

Чтобы понять данный алгоритм, вспомним, что числа являются простыми, если делятся только на единицу и самих себя. Первое простое число - это 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)

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