Алгоритмы поиска простых чисел

СОДЕРЖАНИЕ

 

ВВЕДЕНИЕ………………………………………………………. 3

РЕШЕТО СУНДАРАМА…………………………………………5

РЕШЕТО АТКИНА……………………………………………….6

РЕШЕТО ЭРАТОСФЕНА………………………………………..8

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ…………….11

 

 

ВВЕДЕНИЕ

 

Понятие “алгоритм” давно  является привычным не только для  математиков. Оно является концептуальной основой разнообразных процессов  обработки информации. Возможность  автоматизации таких процессов  обеспечивается наличием соответствующих  алгоритмов. С алгоритмами первое знакомство происходит в нача-льной  школе при изучении арифметических действий с натуральными числами. В  упрощенном понимании “алго-ритм”  – это то, что можно запрограммировать  на ЭВМ.

Слово алгоритм содержит в  своем составе преобразованное  географическое название Хорезм. Термин “алгоритм” обязан своим происхождением великому ученому средневекового Востока - Муххамад ибн Муса ал-Хорезми ( Магомет, сын Моисея, из Хорезма ). Он жил приблизительно с 783 по 850 гг., и в 1983 году отмечалось 1200 летие со дня его рождения в  городе Ургенче – областном центре современной Хорезмской области  Узбекистана. В латинских переводах  с арабского арифметического  трактата ал-Хорезми его имя транскрибировалось как algorismi. Откуда и пошло слово  “алгоритм” – сначала для обозначения  алгоритмов цифровых вычислений десятичной позиционной арифметики, а затем  для обозначения произвольных процессов, в которых искомые величины решаемых задач находятся последовательно  из исходных данных по определенным правилам и инструкциям.

Вплоть до 30-х годов  нашего столетия понятие алгоритма  оставалось интуитивно понятным, имевшем  скорее методологическое, а не математическое значение. Так, к началу ХХ в. много  ярких примеров дала алгебра и  теория чисел. Среди них упомянем алгоритм Евклида нахождения наибольшего  общего делителя двух натуральных чисел  или двух целочисленных многочленов,алгоритм Гаусса решения системы линейных уравнений над полем, алгоритм нахождения рациональных корней многочленов одного переменного с рациональными  коэффициентами, алгоритм Штурма определения числа действительных корней многочлена с действительными коэффициентами на некотором отрезке действительных чисел, алгоритм разложения многочлена одного переменного над конечным полем на неприводимые множители. Указанные алгоритмические проблемы решены путем указания конкретных разрешающих процедур. Для получения результатов такого типа достаточно интуитивного понятия алгоритма. Однако, в начале ХХ в. были сформулированы алгоритмические проблемы, положительное решение которых представлялось маловероятным. Решение таких проблем потребовало привлечения новых логических средств. Ведь одно дело доказать существование разрешающего алгоритма – это можно сделать, используя интуитивное понятие алгоритма. Другое дело – доказать несуществование алгоритма – для этого нужно знать точно – что такое алгоритм.

 

 

 

 

 

 

 

 

 

 

 

 

РЕШЕТО  СУНДАРАМА

 

В математике решето́ Сундара́ма —  детерминированный алгоритм нахождения всех простых чисел до некоторого целого числа . Разработан индийским  студентом С. П. Сундарамом в 1934 году.

Описание

Из ряда натуральных чисел от 1 до N исключаются все числа вида

i + j + 2ij, где индексы  пробегают все натуральные значения, для которых , а именно значения  и  Затем каждое из оставшихся чисел умножается на 2 и увеличивается на 1. Полученная в результате последовательность представляет собой все нечётные простые числа в отрезке [1,2N+1].

Обоснование

Алгоритм работает с нечётными  натуральными числами большими единицы, представленными в виде 2m+1, где m является натуральным числом.

Если число 2m+1 является составным, то оно представляется в виде произведения двух нечётных чисел больших единицы, то есть:

2m+1 = (2i+1)(2j+1)

где i и j — натуральные числа, что  также равносильно соотношению:

m = 2ij+i+j.

Таким образом, если из ряда натуральных  чисел исключить все числа  вида 2ij + i + j, , то для каждого из оставшихся чисел m число 2m+1 обязано быть простым. И, наоборот, если число 2m+1 является простым, то число m невозможно представить в  виде 2ij+i+j и, таким образом, m не будет  исключено в процессе работы алгоритма.

 

 

РЕШЕТО  АТКИНА

 

В математике решето́ А́ткина —  быстрый современный алгоритм нахождения всех простых чисел до заданного  целого числа N. Основная идея алгоритма  состоит в использовании неприводимых квадратичных форм (представление чисел  в виде ax²+by²). Предыдущие алгоритмы  в основном представляли собой различные  модификации решета Эратосфена, где  использовалось представление чисел  в виде редуцированных форм (обычно прозведения xy). Отдельный этап алгоритма  вычеркивает числа, кратные квадратам  простых чисел. Алгоритм был создан А. О. Л. Аткиным (англ.)русск. и Дэниел Ю. Бернштайном (англ.)русск. .

Объяснение

Все числа, равные (по модулю 60) 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, или 58, делятся на два  и заведомо не простые. Все числа, равные (по модулю 60) 3, 9, 15, 21, 27, 33, 39, 45, 51, или 57, делятся на три и тоже не являются простыми. Все числа, равные (по модулю 60) 5, 25, 35, или 55, делятся на пять и также не простые. Все эти  остатки (по модулю 60) игнорируются.

Все числа, равные (по модулю 60) 1, 13, 17, 29, 37, 41, 49 или 53, имеют остаток от деления  на 4 равный 1. Эти числа являются простыми тогда и только тогда, когда  количество решений уравнения 4x² + y² = n нечётно и само число не кратно никакому квадрату простого числа (en:square-free integer).

Числа, равные (по модулю 60) 7, 19, 31, или 43, имеют остаток от деления на 6 равный 1. Эти числа являются простыми тогда и только тогда, когда количество решений уравнения 3x² + y² = n нечётно  и само число не кратно никакому квадрату простого.

Числа, равные (по модулю 60) 11, 23, 47, или 59, имеют остаток от деления на 12 равный 11. Эти числа являются простыми тогда и только тогда, когда количество решений уравнения 3x² − y² = n нечётно и само число не кратно никакому квадрату простого.

Ни одно из рассматриваемых чисел  не делится на 2, 3, или 5, соответственно, они не могут делиться и на их квадраты. Поэтому проверка, что  число не кратно квадрату простого числа, не включает 2², 3², и 5².

Особенности полной версии алгоритма

Сегментация

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

Оценка сложности

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

 

 

 

 

 

 

 

 

 

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

 

Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел до некоторого целого числа n, который  приписывают древнегреческому математику Эратосфену Киренскому.

Алгоритм

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

Выписать подряд все целые числа  от двух до n (2, 3, 4, …, n).

Пусть переменная p изначально равна  двум — первому простому числу.

Считая от p шагами по p, вычеркнуть из списка все числа от 2p до n кратные p (то есть числа 2p, 3p, 4p, …)

Найти первое не вычеркнутое число, большее чем p, и присвоить значению переменной p это число.

Повторять шаги 3 и 4 до тех пор, пока p не станет больше, чем n

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

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

Можно показать, что сложность алгоритма  составляет O(nloglogn) операций в модели вычислений RAM, или O(n(logn)(loglogn)) битовых операций, при условии использования массивов с прямым доступом и вычеркивания каждого кратного числа за время O(1).

Псевдокод

Вход: натуральное число n

Пусть A — булевый массив, индексируемый  числами от 2 до n,

изначально заполненный значением true.

count = n - 1

для i = 2, 3, 4, ..., пока i^2 ≤ n:

  если A[i] = true:

    для j = i^2, i^2 + i, i^2 + 2i, ..., пока j ≤ n:

      если A[j] = true:

        A[j] = false

        count = count - 1

 

Теперь все числа i, такие что A[i] = true, являются простыми,

а переменная count содержит в себе их общее количество в массиве.

Пример для n = 30

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

2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

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

2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

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

2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

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

2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Необходимо провести вычёркивания кратных для всех простых чисел p, для которых. В результате все  составные числа будут вычеркнуты, а невычеркнутыми останутся все  простые числа. Для n = 30 уже после  вычёркивания кратных числу 5 все  составные числа получаются вычеркнутыми:

2  3     5     7           11    13          17    19          23                29

 

СПИСОК  ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

 

1. Решето Аткина [электронный  ресурс]: http://ru.wikipedia.org/wiki/Решето_Аткина
2. Алгоритм нахождения простых чисел [электронный ресурс]: http://habrahabr.ru/blogs/algorithm/122538/
3. Основы теории алгоритмов и анализа их сложности [электронный ресурс]: http://www.intsys.msu.ru/staff/vnosov/theoralg.htm#vvedenie
4. Решето Сундарама [электронный ресурс]: http://ru.wikipedia.org/wiki/Решето_Сундарама
5. Нестеренко Ю. В. Алгоритмические проблемы теории чисел // Введение в криптографию / Под редакцией В. В. Ященко. — Питер, 2001. — 288 с. — ISBN 5-318-00443-1
6. Решето Эратосфена [электронный ресурс]: http://ru.wikipedia.org/wiki/Решето_Эратосфена
7. Решето Эратосфена. Метод поиска простых чисел [электронный ресурс]: http://www.alexeypetrov.narod.ru/C/simple_about.html