Что такое решето в математике

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

В статье рассматриваются понятия простых и составных чисел. Даются определения таких чисел с примерами. Приводим доказательство того, что количество простых чисел неограниченно и произведем запись в таблицу простых чисел при помощи метода Эратосфена. Будут приведены доказательства того, является ли число простым или составным.

Простые и составные числа – определения и примеры

Простые и составные числа относят к целым положительным. Они обязательно должны быть больше единицы. Делители также подразделяют на простые и составные. Чтобы понимать понятие составных чисел, необходимо предварительно изучить понятия делителей и кратных.

Составными числами называют целые числа, которые больше единицы и имеют хотя бы три положительных делителя.

Единица не является ни простым ни составным числом. Она имеет только один положительный делитель, поэтому отличается от всех других положительных чисел. Все целые положительные числа называют натуральными, то есть используемые при счете.

Простые числа – это натуральные числа, имеющие только два положительных делителя.

Составное число – это натуральное число, имеющее более двух положительных делителей.

Натуральные числа, которые не являются простыми, называют составными.

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

Для того, чтобы было проще использовать простые числа, необходимо использовать таблицу:

Рассмотрим теорему, которая объясняет последнее утверждение.

Наименьший положительный и отличный от 1 делитель натурального числа, большего единицы, является простым числом.

Простых чисел бесконечно много.

Видно, что может быть найдено любое простое число среди любого количества заданных простых чисел. Отсюда следует, что простых чисел бесконечно много.

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

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

Перейдем к формулировке теоремы.

Данное число простое или составное?

Перед решением необходимо выяснять, является ли число простым или составным. Зачастую используются признаки делимости. Рассмотрим это на ниже приведенных примере.

Доказать что число 898989898989898989 является составным.

Ответ: 11723 является составным числом.

Источник

Еще раз о поиске простых чисел

В заметке обсуждаются алгоритмы решета для поиска простых чисел. Мы подробно рассмотрим классическое решето Эратосфена, особенности его реализации на популярных языках программирования, параллелизацию и оптимизацию, а затем опишем более современное и быстрое решето Аткина. Если материал о решете Эратосфена предназначен в первую очередь уберечь новичков от регулярного хождения по граблям, то алгоритм решета Аткина ранее на Хабрахабре не описывался.

На снимке — скульптура абстрактного экспрессиониста Марка Ди Суверо «Решето Эратосфена», установленная в кампусе Стэнфорского университета

Введение

Напомним, что число называется простым, если оно имеет ровно два различных делителя: единицу и самого себя. Числа, имеющие большее число делителей, называются составными. Таким образом, если мы умеем раскладывать числа на множители, то мы умеем и проверять числа на простоту. Например, как-то так:
(Здесь и далее, если не оговорено иное, приводится JavaScript-подобный псевдокод)
Время работы такого теста, очевидно, есть O(n ½ ), т. е. растет экспоненциально относительно битовой длины n. Этот тест называется проверкой перебором делителей.

Довольно неожиданно, что существует ряд способов проверить простоту числа, не находя его делителей. Если полиномиальный алгоритм разложения на множители пока остается недостижимой мечтой (на чем и основана стойкость шифрования RSA), то разработанный в 2004 году тест на простоту AKS [1] отрабатывает за полиномиальное время. С различными эффективными тестами на простоту можно ознакомиться по [2].

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

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

Древнегреческий математик Эратосфен предложил следующий алгоритм для нахождения всех простых, не превосходящих данного числа n. Возьмем массив S длины n и заполним его единицами (пометим как невычеркнутые). Теперь будем последовательно просматривать элементы S[k], начиная с k = 2. Если S[k] = 1, то заполним нулями (вычеркнем или высеем) все последующие ячейки, номера которых кратны k. В результате получим массив, в котором ячейки содержат 1 тогда и только тогда, когда номер ячейки — простое число.

Реализация примет следующий вид:

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

Оценим сложность алгоритма. Первое вычеркивание требует n/2 действий, второе — n/3, третье — n/5 и т. д. По формуле Мертенса

так что для решета Эратосфена потребуется O(n log log n) операций. Потребление памяти же составит O(n).

Оптимизация и параллелизация

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

Наращивая шаг прогрессии и количество решет (например, при шаге прогрессии 210 нам понадобится 48 решет, что сэкономит еще 4% ресурсов) параллельно росту n, удается увеличить скорость алгоритма в log log n раз.

Сегментация

Не надо делать ситечки слишком маленькими, меньше тех же O(n ½-ε ) элементов. Так вы ничего не выиграете в асимптотике потребления памяти, но из-за накладных расходов начнете все сильнее терять в производительности.

Решето Эратосфена и однострочники

На Хабрахабре ранее публиковалась большая подборка алгоритмов Эратосфена в одну строчку на разных языках программирования (однострочники №10). Интересно, что все они на самом деле решетом Эратосфена не являются и реализуют намного более медленные алгоритмы.

Дело в том, что фильтрация множества по условию (например, на Ruby) или использование генераторных списков aka list comprehensions (например, на Haskell) вызывают как раз то, избежать чего призван алгоритм решета, а именно поэлементную проверку делимости. В результате сложность алгоритма возрастает по крайней мере до (это число фильтраций), умноженного на (минимальное число элементов фильтруемого множества), где — число простых, не превосходящих n, т. е. до O(n 3/2-ε ) действий.

Однострочник на Scala ближе к алгоритму Эратосфена тем, что избегает проверки на делимость. Однако сложность построения разности множеств пропорциональна размеру большего из них, так что в результате получаются те же O(n 3/2-ε ) операций.

Вообще решето Эратосфена тяжело эффективно реализовать в рамках функциональной парадигмы неизменяемых переменных. В случае, если функциональный язык (например, OСaml) позволяет, стоит нарушить нормы и завести изменяемый массив. В [3] обсуждается, как грамотно реализовать решето Эратосфена на Haskell при помощи техники ленивых вычеркиваний.

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

Запишем алгоритм Эратосфена на PHP. Получится примерно следующее:

Для решения этих проблем достаточно выбрать более подходящий тип данных — строку!

Теперь каждый элемент занимает ровно 1 байт, а время работы уменьшилось примерно втрое. Скрипт для измерения скорости.

Решето Аткина

В 1999 году Аткин и Бернштейн предложили новый метод высеивания составных чисел, получивший название решета Аткина. Он основан на следующей теореме.

Из элементарной теории чисел следует, что все простые, большие 3, имеют вид 12k+1 (случай 1), 12k+5 (снова 1), 12k+7 (случай 2) или 12k+11 (случай 3).

Для инициализации алгоритма заполним решето S нулями. Теперь для каждой пары (x, y), где , инкрементируем значения в ячейках S[4x 2 +y 2 ], S[3x 2 +y 2 ], а также, если x > y, то и в S[3x 2 −y 2 ]. В конце вычислений номера ячеек вида 6k±1, содержащие нечетные числа, — это или простые, или делятся на квадраты простых.

В качестве заключительного этапа пройдемся по предположительно простым номерам последовательно и вычеркнем кратные их квадратам.

Из описания видно, что сложность решета Аткина пропорциональна n, а не n log log n как у алгоритма Эратосфена.

Авторская, оптимизированная реализация на Си представлена в виде primegen, упрощенная версия — в Википедии. На Хабрахабре публиковалось решето Аткина на C#.

Как и в решете Эратосфена, при помощи wheel factorization и сегментации, можно снизить асимптотическую сложность в log log n раз, а потребление памяти — до O(n ½+o(1) ).

О логарифме логарифма

На самом деле множитель log log n растет крайне. медленно. Например, log log 10 10000 ≈ 10. Поэтому с практической точки зрения его можно полагать константой, а сложность алгоритма Эратосфена — линейной. Если только поиск простых не является ключевой функцией в вашем проекте, можно использовать базовый вариант решета Эратосфена (разве что сэкономьте на четных числах) и не комплексовать по этому поводу. Однако при поиске простых на больших интервалах (от 2 32 ) игра стоит свеч, оптимизации и решето Аткина могут ощутимо повысить производительность.

P. S. В комментариях напомнили про решето Сундарама. К сожалению, оно является лишь математической диковинкой и всегда уступает либо решетам Эратосфена и Аткина, либо проверке перебором делителей.

Источник

Решето Эратосфена, попытка минимизировать память

Введение

Одним из алгоритмов для поиска простых чисел является Решето Эратосфена предложенное еще древнегреческим математиком.

Картинка из википедии:

Смысл в вычеркивании чисел кратных уже найденным простым. Остающиеся невычеркнутыми в свою очередь являются простыми. Более подробно расписано тут.

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

Для решения используется сегментация (когда память выделяется по кускам) и другие ухищрения (см. тут).

Реализация алгоритма

Алгоритм внизу (написан на java) предполагает минимальный объем памяти — по сути для каждого найденного простого числа мы храним еще одно число — последнее зачеркнутое (наибольшее). Если я правильно оцениваю объем памяти ln(n) — число найденных простых.

Суть алгоритма:

Допустим мы имеем несколько уже найденных простых чисел отсортированных по возрастанию. (Алгоритм стартует с [2,3]). Для каждого из них храним последнее (наибольшее) зачеркнутое число. Инициализируем самими простыми числами.

Выбираем кандидата в простые например наибольшее найденное простое число +1 (в алгоритме внизу перескакиваем четные как заведомо не простые).

Кандидат сравнивается с последним зачеркнутым текущего простого. Пока текущее зачеркнутое меньше кандидата увеличиваем его на текущее простое. Если текущее зачеркнутое равно кандидату, то кандидат не простое число. Выбираем следующего кандидата.

В случае если текущее зачеркнутое больше кандидата, проверяем кандидата на следующем простом числе.

Если добрались до конца списка простых чисел (то есть все зачеркнутые больше кандидата) мы нашли очередное простое число.

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

Код на java

Тот же код на питоне:

Вся логика традиционных алгоритмов с колесами может быть применена при выборе следующего кандидата.

Возможно это очередное изобретение велосипеда. Готов выслушать замечания.

Источник

РЕШЕТО ЭРАТОСФЕНА

Простые числа. Они так изящны и элегантны. Числа, которые не желают ни в чем принимать участия, которые не размениваются и не делятся, числа, которые остаются сами собой навеки.

Пол Остер

Простые числа – это самые загадочные из всех чисел, открытых математиками. Они делятся только на самих себя и 1, представляют собой некие элементарные частицы мира чисел. Первые несколько из них выделить несложно – 2, 3, 5, 7, 11,13, 17… Более 2000 лет назад Евклид привел изящное доказательство того, что их множество бесконечно.

Решето Эратосфена. Параллельные линии разных цветов, проходящие через таблицу из чисел, вычеркивают все числа, делимые на 3, 5, 7… и кратные им. Числа, через которые не проходит ни одна цветная полоса, являются простыми. Простые числа в начале полос в первом ряду заключены в круги. Четные числа не включены в таблицу, поскольку все они делятся на два

Тем не менее не существует простой волшебной формулы, по которой можно найти их все. Максимальные известные простые числа высоко ценятся математиками и криптографами, поскольку они используются для создания самых надежных в мире шифров. На данный момент максимальным известным простым числом является 230402457 – 1, в полной записи которого 9 152 052 цифры. Оно было найдено Кёртисом Коппером и его коллегами в 2005 году в рамках проекта GIMPS. Это математическая версия онлайн-проекта SETI. В нем используется центральный координирующий сервер, и любой, кто вложит вычислительную мощность своего компьютера в проект поиска простых чисел, получит некие большие числа, чтобы проверить, являются ли они простыми (подобно тому как онлайн-проект SETI передает радиосигналы из космоса, которые можно проанализировать на наличие признаков последовательностей, возможно, имеющих разумное начало). Некоммерческая организация Electronic Frontier Foundation учредила премию в миллион долларов тому, кто первым обнаружит простое число с 10 миллионами цифр. Поиски наибольших простых чисел в значительной мере продвигаются силами крупнейших компьютеров, и их скорость напрямую связана с развитием вычислительной мощности.

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

ЭРАТОСФЕН (К и р е н с к и й) (Ἐρατοσθένης ὁ Κυρηναῖος), ок. 276—194 до н. э.) — древнегреческий учёный. Родился в Кироно. Образование получил в Александрии и Афинах. Заведовал Александрийской библиотекой (после смерти Каллимаха). Работал во многих отраслях науки. В области математики Эратосфен дал известный способ нахождения простых чисел (Эратосфеново решето ), построил прибор для решении задачи об удвоении куба (мезолпбий) и занимался изучением средних величин. Эратосфен заложил основы математической географии; ему принадлежит первое измерение дуги меридиана. Занимался хронологией, астрономией (описание созвездий вместе с соответствующими мифами), филологией (исследование о древней комедии), философией (диалог «Платоник») и музыкой. От сочинений Эратосфена до нас дошли только отрывки.Он возглавлял великую Александрийскую библиотеку и разработал методы для определения окружности Земли и расстояния от нее до Солнца и Луны.

Сведения о решете Эратосфена обнаружены в трактате «Введение в арифметику» сирийского математика Никомеда, написанном около 100 года нашей эры. Это было пособие для школьников гораздо проще «Начал» Евклида, благодаря чему оно широко использовалось вплоть до Средневековья как в Европе, так и в арабском мире. Предложенный Эратосфеном систематический процесс нахождения простых чисел посредством просеивания остальных сквозь решето является первым в математике алгоритмом. Он удобен, пока числа не становятся слишком большими. К сожалению, работы Эратосфена не сохранились и мы можем прочитать о решете только в трудах других авторов, свидетельствующих, что современники считали его великим энциклопедистом, хотя он и не был ведущим авторитетом ни в одной области. По этой причине его прозвали Бетой (В – вторая буква греческого алфавита), или Пентатлосом (так в те времена называли спортсменов-пятиборцев, которые отличились в состязаниях по сумме пяти дисциплин, но не стали чемпионами ни в одной из них в отдельности).

Никомед объясняет решето Эратосфена следующим образом: «Способ решета состоит в следующем. Все нечетные числа, начиная с тройки, последовательно располагаются в ряд, продолжаемый так далеко, насколько это возможно. Начав с первого из них, я смотрю, какие числа оно измеряет, и нахожу, что таковы числа, идущие через два, пока это можно проследить. И оно измеряет не случайно расположенные числа: первое из них отделено от него двумя промежуточными членами, и оно, в соответствии с количеством [единиц] в том числе, с которого начинается ряд, является троекратным; второе отделено от предыдущего еще двумя членами и является пятикратным; третье отделено от предыдущего еще двумя и является семикратным; четвертое отделено от предыдущего еще двумя и является девятикратным и так до бесконечности. Начав заново, я смотрю, какие числа измеряет второе число, и нахожу, что все они отделены друг от друга четырьмя промежуточными членами. Первое из них, в соответствии с количеством [единиц] в том числе, с которого начинается ряд, является троекратным; второе согласно второму является пятикратным; третье согласно третьему является семикратным и так до бесконечности. Ив целом ты можешь действовать так же… И те из них, которые ни разу не окажутся измеренными, но избегают этого, будут первичными и несоставными, просеянными с помощью решета».

Иначе говоря, решето работает так. Запишем все натуральные числа в строки по 10 десяток до максимального интересующего вас числа (назовем его N). Теперь вычеркнем все числа в сетке, которые не являются простыми по правилу Эратосфена. Во-первых, число

1 не считается простым, поэтому исключим его (если бы вы отнесли 1 к простым, в итоге пришлось бы вычеркнуть все числа в списке). Обведем в крут первое из оставшихся чисел –

2 – и вычеркнем последовательно все числа, кратные ему. Таким образом, будут исключены все четные числа. Обведем следующее число – 3 – и вычеркнем все оставшиеся кратные ему. Продолжим аналогичным образом, обводя первое оставшееся число и вычеркивая все кратные ему, которые сохранились к этому моменту. Числа, обведенные в круг, и будут простыми.

Вскоре вы обнаружите, что многие из чисел, намеченных для вычеркивания по причине делимости, например на 7, уже оказываются исключенными, поскольку делятся также на меньшее число (например, 21 = 3 х 7).

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

Наиболее усердным исследователем решета Эратосфена был американский математик Деррик Норман Лемер (1867-1938), опубликовавший таблицы факторизации для первых 10 миллионов простых чисел, выделенных из сетки всех натуральных чисел с помощью решета. Лемер ускорил этот утомительный процесс, частично его механизировав. Его сын построил машину, состоящую из вала, на котором были установлены 30 зубчатых колес со 100 зубьями. Эти колеса сцеплялись с 30 другими колесами с количеством зубьев, соответствующим одному из 30 простых чисел до 127. Вот как работал этот механизм: «Под каждым зубцом в этой второй группе колес находится небольшое отверстие. Когда машина настроена и готова к использованию, некоторые из этих отверстий закрыты, а некоторые – открыты. В сторону машины направляется луч света, после чего она приводится в движение электромотором. Все колеса главного вала вращаются с одинаковой скоростью, но колеса, сцепленные с ними, вращаются с различными скоростями из-за различного количества зубьев. Когда через сотни, а может, и тысячи оборотов одно отверстие каждого колеса оказывается в одной и той же точке в одно и то же время, иначе говоря, когда 30 отверстий выстраиваются в одну линию, луч света проходит сквозь всю машину, попадает на чувствительную фотоэлектрическую пластину и мгновенно останавливает машину. Небольшой счетчик, подсчитывающий количество оборотов главного вала, дает число, по которому легко можно определить все делители анализируемого большого числа».

Один из фактов, которые становятся очевидными при взгляде на изображение решета, заключается в том, что простые числа встречаются тем реже, чем больше они становятся. Это неудивительно. По мере увеличения чисел увеличивается и количество множителей, на которые они могут делиться: например, простым является каждое четвертое число в пределах сотни, каждое шестое число в пределах тысячи, одно из 12,7 в пределах миллиона и только одно из 19,8 в пределах миллиарда. Последовательность такова, что очень приблизительно одно из 2,3N чисел в пределах 10JV является простым. Это можно сказать и иначе: из чисел, меньших N, примерно одно из logN является простым, где logeN – натуральный логарифм JV26. Карл Фридрих Гаусс усовершенствовал эту теорию, предположив, что среди чисел, соседних с N, простым является примерно одно из 1 / logeiV, то есть приблизительно N logN чисел, меньших N, простые. Таким образом, при увеличении N через решето Эратосфена по-прежнему проходит достаточно много чисел. Криптографы не останутся без доступных простых чисел.

Решето Эратосфена, как теоретический метод исследования в теорию чисел был введён только в 1920 норвежским математиком Н. Вруном.

Источник

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

Содержание

Алгоритм

Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:

Теперь все не зачеркнутые числа в списке — простые.

На практике, алгоритм можно несколько улучшить следующим образом. На шаге № 3, числа можно зачеркивать, начиная сразу с числа , потому что все составные числа меньше его уже будут зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда станет больше, чем . [1]

Можно показать, что сложность алгоритма составляет операций в модели вычислений RAM, или битовых операций, [2] [3] при условии вычисления и зачеркивания каждого кратного числа за время , например при использования массивов с прямым доступом.

Неограниченный, постепенный вариант

В этом варианте простые числа вычисляются последовательно, без ограничения сверху, как числа находящиеся в промежутках между составными числами, которые вычисляются для каждого простого числа p начиная с его квадрата, с шагом в p (или для нечетных простых чисел 2p ). [3] [1] Первое простое число 2 (среди возрастающих положит

Перебор делителей

Решето Эратосфена часто путают с алгоритмами, которые отфильтровывают из заданного интервала составные числа, тестируя каждое из чисел-кандидатов с помощью перебора делителей. [4]

Широко известный функциональный код Давида Тёрнера 1975 года [5] часто принимают за решето Эратосфена, [4] но на самом деле это далёкий от оптимального вариант с перебором делителей. [3]

Псевдокод

Пример для

Запишем натуральные числа начиная от 2 до 30 в ряд:

Первое число в списке, 2 — простое. Пройдём по ряду чисел, зачёркивая все числа кратные 2 (то есть каждое второе, начиная с 2 2 = 4 ):

Следующее незачеркнутое число, 3 — простое. Пройдём по ряду чисел, зачёркивая все числа кратные 3 (то есть каждое третье, начиная с 3 2 = 9 ):

Следующее незачеркнутое число, 5 — простое. Пройдём по ряду чисел, зачёркивая все числа кратные 5 (то есть каждое пятое, начиная с 5 2 = 25 ). И т. д.

Решето Эйлера

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

Источник