Решето Эратосфена
Определение. Целое положительное число называется простым, если оно имеет ровно два различных натуральных делителя — единицу и самого себя. Единица простым числом не считается.
Решето Эратосфена (англ. sieve of Eratosthenes) — алгоритм нахождения всех простых чисел от $1$ до $n$.
Основная идея соответствует названию алгоритма: запишем ряд чисел $1, 2,\ldots, n$, а затем будем вычеркивать
- сначала числа, делящиеся на $2$, кроме самого числа $2$,
- потом числа, делящиеся на $3$, кроме самого числа $3$,
- с числами, делящимися на $4$, ничего делать не будем — мы их уже вычёркивали,
- потом продолжим вычеркивать числа, делящиеся на $5$, кроме самого числа $5$,
Самая простая реализация может выглядеть так:
Этот код сначала помечает все числа, кроме нуля и единицы, как простые, а затем начинает процесс отсеивания составных чисел. Для этого мы перебираем в цикле все числа от $2$ до $n$, и, если текущее число простое, то помечаем все числа, кратные ему, как составные.
Если память позволяет, то для оптимизации скорости лучше использовать не вектор bool , а вектор char — но он займёт в 8 раз больше места. Компьютер не умеет напрямую оперировать с битами, и поэтому при индексации к vector он сначала достаёт нужный байт, а затем битовыми операциями получает нужное значение, что занимает приличное количество времени.
Время работы
Довольно легко показать, что асимптотическое время работы алгоритма хотя бы не хуже, чем $O(n \log n)$: даже если бы мы входили в цикл вычёркиваний для каждого числа, не проверяя его сначала на простоту, суммарно итераций было бы
$$ \sum_k \frac
Здесь мы воспользовались асимптотикой гармонического ряда.
У исходного алгоритма асимптотика должна быть ещё лучше. Чтобы найти её точнее, нам понадобятся два факта про простые числа:
Простых чисел от $1$ до $n$ примерно $\frac
Простые числа распределены без больших «разрывов» и «скоплений», то есть $k$-тое простое число примерно равно $k \ln k$.
Мы можем упрощённо считать, что число $k$ является простым с «вероятностью» $\frac<1><\ln n>$. Тогда, время работы алгоритма можно более точнее оценить как
$$ \sum_k \frac<1> <\ln k>\frac
Асимптотику алгоритма можно улучшить и дальше, до $O(n)$.
Линейное решето
Основная проблема решета Эратосфена состоит в том, что некоторые числа мы будем помечать как составные несколько раз — а именно столько раз, сколько у них различных простых делителей. Чтобы достичь линейного времени работы, нам нужно придумать способ, как рассматривать все составные числа ровно один раз.
Обозначим за $d(k)$ минимальный простой делитель числа $k$ и заметим следующий факт: у составного числа $k$ есть единственное представление $k = d(k) \cdot r$, и при этом у числа $r$ нет простых делителей меньше $d(k)$.
Идея оптимизации состоит в том, чтобы перебирать этот $r$, и для каждого перебирать только нужные множители — а именно все от $2$ до $d(r)$ включительно.
Алгоритм
Немного обобщим задачу — теперь мы хотим посчитать для каждого числа $k$ на отрезке $[2, n]$ его минимальный простой делитель $d_k$, а не только определить его простоту.
Изначально массив $d$ заполним нулями, что означает, что все числа предполагаются простыми. В ходе работы алгоритма этот массив будет постепенно заполняться. Помимо этого, будем поддерживать список $p$ всех найденных на текущий момент простых чисел.
Теперь будем перебирать число $k$ от $2$ до $n$. Если это число простое, то есть $d_k = 0$, то присвоим $d_k = k$ и добавим $k$ в список $p$.
Дальше, вне зависимости от простоты $k$, начнём процесс расстановки значений в массиве $d$ — переберем найденные простые числа $p_i$, не превосходящие $d_k$, и сделаем присвоение $d_
Алгоритм требует как минимум в 32 раза больше памяти, чем обычное решето, потому что требуется хранить делитель ( int , 4 байта) вместо одного бита на каждое число. Линейное решето хоть и имеет лучшую асимптотику, но на практике проигрывает также и по скорости оптимизированному варианту решета Эратосфена.
Применения
Массив $d$ позволяет искать факторизацию любого числа $k$ за время порядка размера этой факторизации:
$$ factor(k) = \
Источник
Способ решето эратосфена что это за способ
Тема моей исследовательской работы неразрывно связана с понятием простых чисел. Изучая простые и составные числа на уроках математики в начале 6 класса, я задалась вопросами: «Для чего же нужны простые числа, и где применяется «Решето Эратосфена»?
Поиск простых чисел — по крайней мере, больших простых чисел — довольно сложная задача, потому что еще никому не удалось найти формулу или алгоритм, позволяющий генерировать любые простые числа. Но, может возникнуть логичный вопрос: «Для чего нужно генерировать простые числа?»
На этот вопрос можно дать два ответа. Первый из них имеет теоретическое значение. Попытки генерации простых чисел ведут к появлению новых интересных инструментов для расчетов, особенно для компьютерных вычислений. Кроме того, наличие большого списка простых чисел позволяет проверять теоремы, которые еще не доказаны. Если кто-то выдвигает гипотезу относительно простых чисел, но оказывается, что одно из миллионов чисел нарушает ее, то вопрос снимается. Это стимулирует поиск простых чисел различных видов: простых чисел Мерсенна, чисел-близнецов и так далее. Иногда такой поиск превращается в соревнование, в котором устанавливаются мировые рекорды и за победы присуждаются большие призы.
Но есть и другая, более практическая причина, связанная с так называемым шифрованием. Электронная почта, банковские операции, кредитные карты и мобильная телефонная связь — все это защищено секретными кодами, непосредственно основанными на свойствах простых чисел.
Исходя из этих рассуждений, считаю, что данная тема представляет и сейчас огромный интерес ученых, поэтому актуальность ее очевидна.
Целью моей работы является исследование применения решета Эратосфена в современной жизни.
Исходя из этой цели, в своем исследовании мне предстоит решить следующие задачи:
выяснить актуальность этой темы;
дать определение понятиям, используемым при изучении данной темы;
изучить биографию и труды Эратосфена;
историю возникновения «Решета Эратосфена»;
рассмотреть разнообразие примеров и моделей из жизни, где может пригодиться «Решето Эратосфена»;
Объектом исследования является «Решето Эратосфена», предметом исследования — таблица простых чисел.
Для достижения поставленной цели нами использовались следующие методы исследования:
методы экспериментально-теоретического уровня: анализ и синтез, теоретический анализ литературных источников;
методы эмпирического уровня: анкетирование, сравнение.
В исследовательской работе я хочу проверить следующую гипотезу: «Решето Эратосфена» имеет применение не только для математических вычислений, но и используется в других науках, сферах жизни.
Этапы проекта: теоретический и практический.
2.1. Используемые понятия, актуальные проблемы в исследовании простых чисел
Для изучения данной темы дадим определение основным понятиям, необходимым для ее исследования.
Натуральные числа – это числа, которые используются при счёте предметов: 1,2,3,4,5,……… Все натуральные числа, записанные в порядке возрастания, образуют ряд натуральных чисел. В натуральном ряду за каждым числом следует еще одно число, большее предыдущего на единицу. Как известно, натуральных чисел – бесконечно много.
Простое число — натуральное число, имеющее ровно два различных натуральных делителя — единицу и самого себя. Пр имеры простых чисел: 2,3,5,7,11,13,17,19. Простые числа поставили перед математиками немало сложных вопросов, на многие из которых ответ до сих пор не найден.
Из первой тысячи натуральных чисел 168 чисел являются простыми. Есть простые числа и во второй, третьей, четвертой тысячах. Можно предположить, что среди любых тысячи натуральных чисел, идущих подряд, встречаются простые. Но это не так.
Исследуя таблицы простых чисел, французский математик Жозеф Луи Франсуа Бертран(1822-1900) выдвинул предположение, что при n 1 между числами n и 2 n содержится хотя бы одно простое число. Данный факт смог доказать выдающийся русский математик и механик Пафнутий Львович Чебышёв (1821-1894).
В книге «Начала» древнегреческого учёного Евклида ( III в. до н. э.) доказано, что простых чисел бесконечно много. Математикам до сих пор не удалось найти такое выражение, которое позволило бы получать простые числа друг за другом.
В мире простых чисел существует множество нерешенных задач. Если мы обратимся к учебнику Математика: 6 автора Мерзляка А.Г, то увидим на форзаце таблицу простых чисел, в которой выделены красным цветом простые числа, отличающиеся на 2. Такие пары простых чисел называются близнецами. Но вычислить, сколько пар таких близнецов, конечно это количество или бесконечно, пока не удалось никому.
Также неизвестно, сколько на данный момент существует простых чисел, состоящих только из единиц, и конечно или бесконечно множество простых чисел, в записи которых нет ни одного нуля.
Составным числом называется натуральное число , большее, чем единица, которое не является простым . Каждое составное число является произведением двух или более натуральных чисел, больших 1. Перечислим подряд несколько составных чисел: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25.
А число 1 имеет только один делитель — само это число, поэтому оно не относится ни к простым, ни к составным числам. Таким образом, множество натуральных чисел состоит из простых чисел, составных чисел и единицы. [3]
Разберем, что же такое решето, и почему данное слово используется в математике. Когда в каком-то веществе или продукте необходимо отделить мелкие частички от более крупных, то используют решето. Например, после помола зерна с помощью решета отделяют муку от отрубей.
Согласно «Толковому словарю» Д.Н. Ушакова, решето — это утварь для просеивания муки, состоящая из широкого обруча и натянутой на него с одной стороны сетки. [7] В Толковом словаре Ожегова, решетом называется предмет обихода, широкий обруч с натянутой на него частой сеткой для просеивания чего-нибудь. [6]
В «Новом словаре русского языка» Ефремовой Т.Ф, решетом называется предмет хозяйственной утвари в виде широкого деревянного обода с натянутой на одну сторону крупной сеткой, употребляемый для просеивания муки. [5]
Древнегреческий математик Эратосфен придумал, как отделить простые числа в ряду натуральных чисел. Его метод получил название «решето Эратосфена».
2.2 История жизни и деятельность великого Эратосфена
Первым проблему определения простых чисел обозначил и решил древнегреческий ученый Эратосфен Киренский, примерно в 220 году до нашей эры, предложив один из алгоритмов определения простых чисел. Этот способ назвали «решетом Эратосфена». (Рис. 1)
Рис. 1 Эратосфен
Эратосфен — древний математик, живший в 276-194 годах до нашей эры. Он является одним из самых разносторонних ученых античности. История сохранила краткие сведения из биографии Эратосфена, однако на него очень часто ссылались авторитетные и знаменитые мудрецы, философы античности: Архимед, Страбон и другие. Родился Эратосфен в Африке, в Кирене, поэтому нет ничего удивительного в том, что своё образование он начал в Александрии. Живой ум Эратосфена пытался постичь практически все известные на тот момент науки. И как все учёные, он наблюдал за природой. [2]
Эратосфен заложил основы математической географии, вычислив с большой точностью величину земного шара, изобрел широту и долготу, а так же придумал високосный день.
Особенно прославили Эратосфена труды по астрономии, географии и математике, однако он успешно трудился и в области филологии, поэзии, музыки и философии, за что современники дали ему прозвище «Пентатл», т.е. многоборец. Другое его прозвище, «Бета», т.е. «второй», по-видимому, также не содержит ничего уничижительного: им желали показать, что во всех науках Эратосфен достигает не высшего, но превосходного результата.
Из сочинений Эратосфена по математике до нашего времени дошло только написанное к царю Птолемею письмо об удвоении куба. Это письмо сохранилось в комментарии Евтокия к трактату Архимеда о шаре и цилиндре.
Но самым знаменитым математическим открытием Эратосфена стало так называемое «решето Эратосфена», с помощью которого находятся простые числа. Эратосфена можно считать также основателем научной хронологии . В своих хронографиях он пытался установить даты, связанные с политической и литературной историей Древней Греции , составил список победителей Олимпийских игр. В трактате «О древней комедии » , где анализировались произведения афинских драматургов , Эратосфен выступил как литературный критик и филолог .
Эратосфен написал также поэму « Гермес » , повествующую о рождении, подвигах и гибели бога, до нас дошли ее фрагменты. Другой короткий эпос, « Гесиод » , посвящен смерти поэта и каре, постигшей его убийц . Эратосфен написал также трактат «Катастеризмы» — это описание созвездий , изложение посвященных им мифов . Эратосфену принадлежал еще ряд работ по истории и философии, которые не сохранились.
Математиков и после смерти Эратосфена волновала проблема нахождения простых чисел. В 1909 году американский математик Деррик Норман Лемер опубликовал таблицы простых чисел в промежутке от 1 до 10.017.000. Книга таблиц имеется в Российской государственной библиотеке в Москве. [1]
Еще более титаническую вычислительную работу выполнил профессор Парижского университета славянский математик Якуб Филипп Кулик (01.05.1793- 28.02.1863). Над своей рукописью «Великий канон делителей всех чисел, не делящихся на 2, 3 и 5, и заключенных между ними простых чисел до 100 300 201» он работал последние 20 лет жизни, не имея никакой надежды на его издание. Это произведение до сих пор не напечатано. Оно хранится в библиотеки Венской Академии Наук.
Разработанный способ нахождения простых чисел «решето Эратосфена» получил такое название потому, что, согласно легенде, Эратосфен писал числа на дощечке, покрытой воском, и прокалывал дырочки в тех местах, где были написаны составные числа. (Приложение I ) Поэтому дощечка являлась неким подобием решета, через которое «просеивались» все составные числа, а оставались только числа простые.
2.3 Применение «решета Эратосфена» в современной жизни
Быстрый способ найти все простые числа в натуральном ряду интересовали ученых с незапамятных времен. Ведь они не имеют строгой последовательности и расположены в условно-случайном порядке. На данный момент специалисты во многом разобрались и научились производить нужные вычисления достаточно быстро. В этом им помог исследуемый алгоритм – «решето Эратосфена».
Разберем, что представляет собой этот алгоритм. Покажем, как из первой сотни натуральных чисел «просеять» простые числа:
Запишем первые сто натуральных чисел в виде таблицы.
Зачеркнём в этой таблице число 1, которое не является простым. Далее обведём число 2, а остальные чётные числа таблицы зачеркнём. (Приложение II )
Первым из оставшихся чисел будет число 3, которое мы тоже обведём. Далее вычеркнем из таблицы все числа, кратные трём, кроме самого числа 3. (Приложение III )
Первым из оставшихся чисел будет число 5. Далее проделаем такую же операцию с числами 5 и 7. (Приложение IV )
На этом этапе просеивание завершено. Все оставшиеся числа в таблице являются простыми. Действительно, числа 4,6,8,9,10 оказались вычеркнутыми. Если составное число больше 10, но меньше 100, то его можно представить в виде произведения двух множителей, один из которых меньше 10. Составное число с таким множителем кратно одному из чисел 2,3,5,7, а значит, будет вычеркнуто.
Мы выяснили, что «Решето Эратосфена» работает как своего рода аналоговая вычислительная машина. Оно нужно для просеивания простых чисел от составных. Все это пригождается в математике.
Посмотрев интернет источники, я обнаружила сайт, на котором говорилось, что решето используется не только в математике, но и в информатике. Технологии, компьютеры и информатика позволили математикам, изучающим алгебраические теории, выйти на новый этап развития науки. Первым делом, воспользовавшись уникальной возможностью, они стали интегрировать известные арифметические и геометрические исследования в программирование.
Одним из самых востребованных электронно-вычислительных языков в тот момент стал, в том числе для расчета алгоритма «решета Эратосфена», Паскаль. С его помощью за несколько секунд можно было находить простые числа в последовательности натуральных цифр, которые долгое время были недоступны или исчислялись путем грандиозных записей, занимая много времени. В итоге, практическая база нового потенциала получила улучшенный вариант античного открытия и практические безграничные возможности расчетов.
На данный момент проведение соревнований для школьников по различным предметам снова набирают популярность. Лауреаты и победители таких мероприятий выходят на новый уровень обучения и могут получить неплохие перспективы в дальнейшей деятельности, в том числе материальные гранды.
Олимпиады по информатике включают в себя не только сложные задачи, но и нахождение таких известных понятий, как простые числа. Решето Эратосфена при этом используется в качестве наиболее актуального способа вычисления последовательностей, путем интегрирования аксиомы в программный код. Несмотря на древность открытия, данная теория помогает быстро и эффективно освоиться в труднодоступных расчетах.
Очевидно, что компьютерная реализация «решета Эратосфена» требует большого объёма памяти. Так оно и было, пока своё решение проблемы не предложил современный 38-летний перуанский математик в Харальд Хельфготт , которому удалось предложить улучшенный вариант «решета Эратосфена» — метода поиска простых чисел.
Новый вариант в компьютерной реализации требует меньше оперативной памяти, что означает меньший объём подкачки страниц из виртуальной памяти — следовательно, процесс существенно ускоряется.
2.4 Практическая часть
Я провела анкетирование в двух классах шестой параллели МАОУ СОШ № 73 г. Челябинска, чтобы узнать, насколько актуальна данная тема, и что учащиеся вообще об этом знают. В анкетировании приняли участие 43 человека. Учащимся было задано три вопроса, на которые было предложено дать краткий ответ: да или нет. Результаты анкетирования следующие:
Знаете ли Вы, что представляет собой решето, для чего оно используется?
Да: 5 человек, нет: 38 человек.
Знаете ли Вы, что такое простые числа, составные числа?
Да: 21 человек, нет: 22 человека.
Известно ли Вам, что такое «решето Эратосфена», как его применять?
Да: 9 человек, нет: 34 человека.
Исходя из результатов анкетирования, я пришла к выводу, что многие учащиеся не обладают знаниями по данной теме, а также не имеют представления, что представляет собой «решето Эратосфена» и для чего оно применяется. Хотя данная тема изучается в 6 классе, и знание простых чисел необходимо для изучения последующих тем курса математики.
Рис.2 Доска для просеивания простых чисел
Далее учащимся был показан способ нахождения простых чисел – «просеивание» простых чисел на изготовленной доске, где расположены последовательно числа от 0 до 100. (Рис. 2) Учащиеся смогли убедиться, что, действительно данный способ работает и позволяет искать простые числа в пределах первой сотни.
Математика – наука, которая появилась несколько тысяч лет и активно использовалась уже в Древней Греции. При этом многие ученые-теоретики, жившие в то время, делали открытия, ставшие великими и гениальными, но настоящее признание получили несколько веков спустя, когда технологии позволили понять весь потенциал исследований античных арифметиков.
Стоит отметить, что все расчеты в далеких эпохах велись «в уме» или содержали в себе масштабные записи вычислений. Одним из самых известных греческих специалистов был Эратосфен, негласно названный прапрадедушкой программирования.
С появлением информатики именно его расчеты, теории и аксиомы нередко преобразовывались в компьютерные «языки». В арсенале математика было несколько интересных открытий, но наиболее распространенным стало решето Эратосфена, помогающее быстро найти простое число из представленной последовательности.
«Решето Эратосфена» работает, как вычислительная машина. Так, значит, Эратосфен изобрел счётную машину. Эта счётная машина используется в математике и считается предметом для точного вычисления простых чисел. Также «Решето Эратосфена» используется в информатике как язык программирования и в олимпиадах по информатике.
Итак, я узнала, что «Решето Эратосфена» используется в современной жизни программистов и в жизни школьников, а также, что Харальд Хельфготт смог оптимизировать его, для меньшего расхода памяти на компьютере.
Я считаю, что сформулированные цели в моей исследовательской работе выполнены, а гипотеза исследования подтверждена.
Список используемой литературы:
Гальперин Г. «Просто о простых числах» // Квант . — № 4 .
Грасиан Э. Простые числа. Долгая дорога к бесконечности. Мир математики. / Энрике Грасиан. — М.: ООО «Де Агостини», 2014. – 64 с.
Мерзляк А.Г. Математика: 6 класс: учебник / А.Г. Мерзляк, В.Б. Полонский, М.С. Якир; под ред. В.Е. Подольского. — М. : Вентана — Граф, 2019. – 334 с.
Простое число // Математическая энциклопедия (в 5 томах) . — М. : Советская Энциклопедия, 1977. — Т. 4.
Толково-образовательный. Новый словарь русского языка Ефремова Т.Ф. — М.: Рус. яз., 2000.- 1209 с.
Толковый словарь русского языка: Ок. 100 000 слов, терминов и фразеологических выражений / С. И. Ожегов; под ред. проф. Л. И. Скворцова. — М.: ООО Издательство «Мир и Образование» , 2012. — 1376 с.
Ушаков Д.Н Толковый словарь / Д.Н. Ушаков. — М.: Славянский Дом Книги , 2014 г. – 960с.
Приложение I Решето Эратосфена
Приложение II Таблица натуральных чисел № 1
Приложение III Таблица натуральных чисел № 2
Приложение IV Таблица натуральных чисел № 3
Источник
