Способ эратосфена для простых чисел

Решето Эратосфена — алгоритм определения простых чисел

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

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

Источник

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

Определение. Целое положительное число называется простым, если оно имеет ровно два различных натуральных делителя — единицу и самого себя. Единица простым числом не считается.

Решето Эратосфена (англ. 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 = \frac <2>+ \frac <3>+ \frac <4>+ \ldots + \frac = O(n \log n) $$

Здесь мы воспользовались асимптотикой гармонического ряда.

У исходного алгоритма асимптотика должна быть ещё лучше. Чтобы найти её точнее, нам понадобятся два факта про простые числа:

Простых чисел от $1$ до $n$ примерно $\frac<\ln n>$ .

Простые числа распределены без больших «разрывов» и «скоплений», то есть $k$-тое простое число примерно равно $k \ln k$.

Мы можем упрощённо считать, что число $k$ является простым с «вероятностью» $\frac<1><\ln n>$. Тогда, время работы алгоритма можно более точнее оценить как

$$ \sum_k \frac<1> <\ln k>\frac \approx n \int \frac<1> = n \ln \ln k \Big |_2^n = O(n \log \log n) $$

Асимптотику алгоритма можно улучшить и дальше, до $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_ = p_i$.

Алгоритм требует как минимум в 32 раза больше памяти, чем обычное решето, потому что требуется хранить делитель ( int , 4 байта) вместо одного бита на каждое число. Линейное решето хоть и имеет лучшую асимптотику, но на практике проигрывает также и по скорости оптимизированному варианту решета Эратосфена.

Применения

Массив $d$ позволяет искать факторизацию любого числа $k$ за время порядка размера этой факторизации:

$$ factor(k) = \ \cup factor(k / d(k)) $$ Знание факторизации всех чисел — очень полезная информация для некоторых задач. Линейное решето интересно не своим временем работы, а именно этим массивом минимальных простых делителей.

Источник

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

Определение. Целое положительное число называется простым, если оно имеет ровно два различных натуральных делителя — единицу и самого себя. Единица простым числом не считается.

Решето Эратосфена (англ. 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 = \frac <2>+ \frac <3>+ \frac <4>+ \ldots + \frac = O(n \log n) \]

Здесь мы воспользовались асимптотикой гармонического ряда.

У исходного алгоритма асимптотика должна быть ещё лучше. Чтобы найти её точнее, нам понадобятся два факта про простые числа:

Простых чисел от \(1\) до \(n\) примерно \(\frac<\ln n>\) .

Простые числа распределены без больших «разрывов» и «скоплений», то есть \(k\) -тое простое число примерно равно \(k \ln k\) .

Мы можем упрощённо считать, что число \(k\) является простым с «вероятностью» \(\frac<1><\ln n>\) . Тогда, время работы алгоритма можно более точнее оценить как

\[ \sum_k \frac<1> <\ln k>\frac \approx n \int \frac<1> = n \ln \ln k \Big |_2^n = O(n \log \log n) \]

Асимптотику алгоритма можно улучшить и дальше, до \(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_ = p_i\) .

Алгоритм требует как минимум в 32 раза больше памяти, чем обычное решето, потому что требуется хранить делитель ( int , 4 байта) вместо одного бита на каждое число. Линейное решето хоть и имеет лучшую асимптотику, но на практике проигрывает также и по скорости оптимизированному варианту решета Эратосфена.

Применения

Массив \(d\) он позволяет искать факторизацию любого числа \(k\) за время порядка размера этой факторизации:

\[ factor(k) = \ \cup factor(k / d(k)) \]

Знание факторизации всех чисел — очень полезная информация для некоторых задач. Ленейное решето интересно не своим временем работы, а именно этим массивом минимальных простых делителей.

Источник

Способ эратосфена для простых чисел

Главная
• Список секций
• Математика
• ПРОСТЫЕ ЧИСЛА И РЕШЕТО ЭРАТОСФЕНА

ПРОСТЫЕ ЧИСЛА И РЕШЕТО ЭРАТОСФЕНА

Автор работы награжден дипломом победителя III степени

Введение

Впервые о простых числах мы узнали в 6 классе на уроке математики, когда изучали тему «Простые и составные числа». Так же на форзаце учебника «Математика-6» имеется таблица простых чисел до числа 997 (Приложение 1). Мы знаем то, что находится на форзаце, имеет важную значимость в изучении данного предмета. И действительно, это подтвердилось при дальнейшем изучении математики

Мы заинтересовались происхождением простых чисел, алгоритмами нахождения простых чисел, алгоритмом создания таблиц простых чисел, в частности, «решетом Эратосфена».

Работу начали с анкетирования учащихся 6 – 10 классов нашей школы, чтобы выяснить знают ли они:

1. Что такое решето?

2. Какие числа называются простыми?

3. Кто такой Эратосфен?

4. Что такое «решето Эратосфена»?

В опросе приняли участие 90 человек. Результаты оказались следующими (Приложение 2).

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

Гипотеза: Действительно ли мы можем найти простое число больше 997.

Цель работы: изучить алгоритм построения «решета Эратосфена» и изготовить его материальную модель для использования на уроках математики.

Задачи:

1.Изучить имеющуюся литературу по теме проекта.

2.Провести опрос по теме проекта.

3.Найти простые числа, больше числа 997.

4.Изготовить материальную модель решета Эратосфена.

Объект исследования: простые числа, «решето Эратосфена»

Предмет исследования: таблица простых чисел

Методы исследования:

1.Работа с учебной и научно-популярной литературой, ресурсами сети Интернет.

3. Опыты и эксперименты с простыми числами

Этапы проекта:

2. Основная часть

2.1. Краткое описание используемых понятий

Решето – это утварь для просеивания муки, состоящая из широкого обруча и натянутой на него с одной стороны сетки. Решето отличается от сита более крупным размером отверстий сетки. (Толковый словарь Ушакова)

Решето -1) Предмет обихода широкий обруч с натянутой на него частой сеткой для просеивания чего-нибудь

2) Просеивающее устройство. (Толковый словарь Ожегова)

Решето – всякая несплошная вещь со сквозниной, с промежками, пролётами; ряд установленных жёрдочек, шестиков…переплетённых вдоль и поперёк, или иным образом.(Толковый словарь Даля)

Простое число – это натуральное число, которое не имеет других делителей кроме 1 и самого себя. (Пример: число 19 = 1 * 19)

Составное число – это натуральное число, у которого есть делители,отличные от 1 и самого себя. (Пример: число 10 = 5*2)

Всякое составное число можно разложить на простые множители.(Например: 63=3*3*7 или 363= 3*11*11)

Число 1 имеет только один делитель: само это число. Поэтому оно не относит ни к простым, ни к составным числам.

Первым проблему определения простых чисел обозначил и решил древнегреческий ученый Эратосфен Киренский примерно в 220 году до нашей эры, предложив один из алгоритмов определения простых чисел. Этот способ назвали «решето Эратосфена».

В 1909 году американский математик Деррик Норман Лемер опубликовал таблицы простых чисел в промежутке от 1 до 10.017.000. Книга таблиц имеется в Российской государственной библиотеке в Москве.

Еще более титаническую вычислительную работу выполнил профессор Парижского университета славянский математик Якуб Филипп Кулик (01.05.1793- 28.02.1863).Над своей рукописью «Великий канон делителей всех чисел, не делящихся на 2, 3 и 5, и заключенных между ними простых чисел до 100 300 201» он работал последние 20 лет жизни, не имея никакой надежды на его издание. Это произведение до сих пор не напечатано. Оно хранится в библиотеки Венской АкадемииНаук.

2.2. Биография Эратосфена

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

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

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

Его научные таланты удостоились высокой оценки современника Эратосфена, Архимеда, который посвятил ему свою книгу Эфодик (т.е. Метод)

2.3. Из истории появления «решета Эратосфена»

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

1.Из ряда чисел: 2,3,4,5,6,7,8,9,10,11,12,13 и т. д вычёркиваем числа кратные 2.

2.Затем, вычёркиваем числа кратные 3.

3.Вычёркиваем числа кратные 4.

4.Вычёркиваем числа кратные 5.

5.Вычёркиваем числа кратные 6 .

6.Делим, пока все составные числа не будут «просеяны», и останутся только простые числа: 2,5,7,11,.13….

Пример

Запишем натуральные числа, начиная от 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

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

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

2.4. Практическая часть проекта: изготовление решета Эратосфена

Для изготовления «решета Эратосфена» мы взяли фанеру формата 36*42. Начертили сетку, в каждой клетке записали натуральные числа от 1001 до 1120.

Используя алгоритм построения «решета Эратосфена», проделали отверстия в тех клетках, в которых указаны составные числа.(Приложение 3)

Заключение

Мы изучили алгоритм построения «решета Эратосфена», изготовили его материальную модель, изучили литературу и провели опрос. Подтвердили гипотезу, что можно найти простое число, больше чем 997.

Следовательно – наша цель достигнута, проблема решена. Разработанные нами материалы могут использоваться на уроках математики.

Список использованной литературы

Я познаю мир. Детская энциклопедия: Математика/ Я 11 Авт.-сост. А.П. Савин и др.: — М.: ООО «Издательство АСТ», 2001.

Интернет – ресурсы( Википедия)

А.Г. Мерзляк, В.Б. Полонский, М.С. Якир. Учебник «Математика 6 класс»:Издательство «Вентана–Граф», Москва, 2014

Толковый словарь Ушакова

Толковый словарь Ожегова

Толковый словарь Даля

Приложение 1

таблица простых чисел

Приложение 2

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

1. Что такое решето?

2. Какие числа называются простыми?

3. Кто такой Эратосфен?

4. Что такое «решето Эратосфена»?

В опросе приняли участие 90 человек. Результаты оказались следующими.

Вопрос

«да»

«нет»

Знаете ли вы что такое решето?

Знаете ли вы какие числа называются простыми?

Знаете ли вы кто такой Эратосфен?

Знаете ли вы что такое «решето Эратосфена»?

Источник