Алгоритм распознавания простых чисел

Простые числа – это натуральные числа, большие единицы, которые имеют только два делителя: единицу и само это число.

Примеры простых чисел: 2 , 3, 5, 7, 11, 13…

(Единица не является простым числом!)

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

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

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

Задача 1. Определение простого числа.

Составить программу, которая будет проверять, является ли введенное число простым.

Самый простой путь решения этой задачи – проверить, имеет ли данное число n (n >= 2) делители в интервале [2; n-1]. Если делители есть, число n – составное, если – нет, то – простое. При реализации алгоритма разумно делать проверку на четность введенного числа, поскольку все четные числа делятся на 2 и являются составными числами, то, очевидно, что нет необходимости искать делители для этих чисел. Логическая переменная flag в программе выступает в роли “флаговой” переменной и повышает наглядность программы, так, если flag = true, то n –простое число; если у числа n есть делители, то “флаг выключаем” с помощью оператора присваивания flag:= false, таким образом, если flag = false, то n – составное число.

Задача 2. Нахождение простых чисел в заданном интервале.

Составить программу, которая напечатает все простые числа в заданном интервале [2, m], для m>3 и подсчитает их количество.

Для реализации данного алгоритма необходимо проверить каждое число, находящееся в данном интервале, — простое оно или нет. Однако для этого машине пришлось бы потратить много времени. Поэтому подумаем, каким образом можно оптимизировать алгоритм, описанный в задаче 1, применительно к задаче 2?

Будем использовать следующие приемы оптимизации алгоритма:

  1. рассматривать только нечетные числа;
  2. использовать свойство: наименьшее число, на которое делится натуральное число n, не превышает целой части квадратного корня из числа n;
  3. прерывать работу цикла, реализующего поиск делителей числа, при нахождении первого же делителя с помощью процедуры Break, которая реализует немедленный выход из цикла и передает управление оператору, стоящему сразу за оператором цикла.

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

Счетчик чисел будет находиться в переменной k. Когда очередное простое число найдено, он увеличивается на 1. Простые числа выводятся по 10 в строке, как только значение счетчика становится кратным 10, курсор переводится на новую строку.

Близнецы

Два нечетных простых числа, разнящихся на два, называются близнецами. Близнецами являются, например, числа 5 и 7, 11 и 13, 17 и 19 и т.д. В начале натурального ряда такие пары чисел встречаются достаточно часто, но, по мере того как мы продвигаемся в область больших чисел, их становится все меньше и меньше. Известно, что в первой сотне имеется целых 8 близнецов, дальше они расположены очень неравномерно, их можно обнаружить все реже и реже, гораздо реже, нежели сами простые числа. До сих пор неясно, конечно ли число близнецов. Более того, еще не найден способ, посредством которого можно было бы разрешить эту проблему.

Задача 3. Поиск пар чисел близнецов.

Написать программу, которая будет находить все числа близнецы в интервале [2; 1000] и подсчитывать количество пар чисел близнецов.

Фактически будем использовать алгоритм и программу Задачи 2. В этом алгоритме нужно использовать дополнительные переменные для хранения двух “последних” простых чисел и проверять условие наличия близнецов – их разность должна быть равна двум.

Задача 4. Нахождение простых чисел в заданном интервале с выводом в выходной файл.

Реализовать алгоритм задачи 2 с выводом простых чисел в выходной файл по 10 в строке. Последняя строка файла должна содержать информацию о количестве простых чисел в заданном интервале.

Задача 5. Приемы оптимизации алгоритма задачи 4.

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

Словесное описание алгоритма:

  1. Вводим правую границу диапазона – m;
  2. Записываем двойку и тройку в файл;
  3. Пока очередное нечетное число i m ), вывести в файл количество простых чисел.

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

Греческий математик Эратосфен (275-194 гг. до н.э.) предложил интересный метод нахождения простых чисел в интервале [2; n]. Он написал на папирусе, натянутом на рамку, все числа от 2 до 10000 и прокалывал составные числа. Папирус стал, как решето, которое “просеивает” составные числа, а простые оставляет. Поэтому такой метод называется Эратосфеновым решетом. Рассмотрим подробнее этот метод.

Читайте также:  Приложение для формата rar

Пусть написаны числа от 2 до n:

Первое неперечеркнутое число в строке является простым. Таким образом, 2 – простое число. Начинаем “просеивание” с него, перечеркивая все числа, которые делятся на 2:

Далее берем следующее по порядку неперечеркнутое число и перечеркиваем все числа, кратные ему и т. д. Таким образом, мы перечеркнем все составные числа, а простые останутся неперечеркнутыми:

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

Задача 6. Нахождение простых чисел с помощью решета Эратосфена.

Реализовать алгоритм решета Эратосфена с помощью организации работы с множествами.

Словесное описание алгоритма:

  1. Выделим из первых n натуральных чисел все простые числа (решето Эратосфена).
  2. Вначале формируем множество BeginSet, состоящее из всех целых чисел в диапазоне от 2 до n. Множество PrimerSet будет содержать искомые простые числа.
  3. Затем циклически повторим действия:
  1. взять из BeginSet первое входящее в него число next и поместить его в PrimerSet;
  2. удалить из BeginSet число next и все другие числа, кратные ему, т. е. 2* next, 3* next и т. д.

Цикл повторяется до тех пор, пока множество BeginSet не станет пустым. Программу нельзя использовать для произвольного n, т. к. в любом множестве не может быть больше 256 элементов. (Для расширения интервала простых чисел можно разбить одно большое множество на несколько маленьких, т. е. представить большое множество в виде массива малых множеств. Этот случай рассматривать не будем. Можно предложить наиболее заинтересованным учащимся самостоятельно рассмотреть этот вариант.)

Литература:

  1. Е.В. Андреева Методика обучения основам программирования на уроках информатики. Лекции 1-8. – М.: Педагогический университет «Первое сентября», 2006.
  2. В.А. Дагене, Г.К. Григас, А.Ф. Аугутис 100 задач по программированию. – М.: Просвещение, 1993. — 255 с.
  3. В.В. Фаронов Турбо Паскаль 7.0. Начальный курс. Учебное пособие. – М.: «Нолидж», 1999. — 616 с.

Презентация была опубликована 7 лет назад пользователемwww.itlab.unn.ru

Похожие презентации

Презентация на тему: " О БЗОР АЛГОРИТМОВ ПОИСКА И РАСПОЗНАВАНИЯ ПРОСТЫХ ЧИСЕЛ, ИНФОРМАЦИЯ ОБ ИХ ПРИМЕНИМОСТИ. Курицын Михаил Люлькова Елена Сизов Илья." — Транскрипт:

1 О БЗОР АЛГОРИТМОВ ПОИСКА И РАСПОЗНАВАНИЯ ПРОСТЫХ ЧИСЕЛ, ИНФОРМАЦИЯ ОБ ИХ ПРИМЕНИМОСТИ. Курицын Михаил Люлькова Елена Сизов Илья

2 С ОДЕРЖАНИЕ Простое число Зачем искать простые числа? Алгоритмы поиска простых чисел Сравнение алгоритмов поиска простых чисел Алгоритмы распознавания простых чисел. Тесты простоты. Алгоритмы распознавания простых чисел. Тесты простоты. Сравнение тестов простоты Список литературы 2

3 П РОСТОЕ ЧИСЛО Простое число – это натуральное число, которое имеет ровно два различных натуральных делителя: единицу и самого себя. Остальные числа, кроме единицы, называются составными. Последовательность простых чисел начинается так: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, … 3

4 С АМОЕ БОЛЬШОЕ ПРОСТОЕ ЧИСЛО Один из рекордов поставил в своё время Эйлер, найдя простое число = Наибольшим известным простым числом по состоянию на февраль 2011 года является За нахождение простых чисел из более чем и десятичных цифр EFF назначила денежные призы соответственно в и долларов. 4

5 З АЧЕМ ИСКАТЬ ПРОСТЫЕ ЧИСЛА ? Криптография – наука о методах обеспечения конфиденциальности (невозможности прочтения информации посторонним) и аутентичности (целостности и подлинности авторства) информации. Криптография изучает методы шифрования информации – преобразования открытого текста на основе секретного алгоритма и/или ключа в шифрованный текст. В криптографических алгоритмах одной из важных задач является проверка на простоту, т.е. умение быстро отличить просто число от составного. 5

6 А ЛГОРИТМЫ ПОИСКА ПРОСТЫХ ЧИСЕЛ Простые способы нахождения начального списка простых чисел вплоть до некоторого значения дают : Решето Эратосфена Решето Сундарама Решето Аткина 6

7 7 Р ЕШЕТО Э РАТОСФЕНА Алгоритм: 1.Пусть p = 2 (первому простому числу). 2.Считая от р, шагами по р, зачеркнуть в списке все числа от 2р до n. 3.Найти первое не зачеркнутое число, большее чем p, и присвоить значение переменной p это число. 4.Повторять шаги 3 и 4 до тех пор, пока p не станет больше чем n. Простые числа: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.

8 Р ЕШЕТО Э РАТОСФЕНА Сложность алгоритма: 8

9 Р ЕШЕТО С УНДАРАМА i = 1, j = 1,…,6; i = 2, j = 1,2,3; Простые числа: 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41.

10 Р ЕШЕТО С УНДАРАМА. О БОСНОВАНИЕ Алгоритм работает с нечётными натуральными числами большими 1, представленными в виде 2 m +1, где m является натуральным числом. Если число 2 m +1 является составным, то оно представляется в виде произведения двух нечётных чисел больших единицы, то есть: 10 2 m +1 = (2 i +1)(2 j +1), где i, j – натуральные числа m = 2 ij + i + j Что эквивалентно: Если из ряда натуральных чисел исключить все числа вида 2ij + i + j,, то для каждого из оставшихся чисел m число 2 m +1 обязано быть простым. Если число 2 m +1 является простым, то число m невозможно представить в виде 2 ij + i + j и, таким образом, m не будет исключено в процессе работы алгоритма.

11 Р ЕШЕТО А ТКИНА B основу алгоритма "решета Аткина" положены три стандартные теоремы теории элементарных чисел:

12 А ЛГОРИТМ Создать решето (массив соответствия простым числам для всех положительных, целых чисел начиная с 2). Изначально все элементы решета помечаются как составные. Для каждого числа n в решете, если остаток от деления по модулю 60: Равен 1, 13, 17, 29, 37, 41, 49, или 53, и n = 4 * x 2 + y 2 поменять значение в решете на противоположное. Равен 7, 19, 31, или 43, и n = 3 * x 2 + y 2 ; поменять значение решете на противоположное. Равен 11, 23, 47, или 59, и n = 3 * x 2 — y 2 при(x > y); поменять значение в решете на противоположное. (х и у целые, положительные числа) Взять наименьшее число из решета, помеченное как простое, и пометить все элементы решета, кратные квадрату этого простого числа как составные. Повторить шаг 3 12 y); поменять значение в решете на противоположное. (х и у целые, положительные числа) Взять наименьшее число из решета, помеченное как простое, и пометить все элементы решета, кратные квадрату этого простого числа как составные. Повторить шаг 3 12">

Читайте также:  Скрипт для world of tanks

13 Р ЕШЕТО А ТКИНА Алгоритм имеет асимптотическую сложность: 13 и требует следующее кол-во бит памяти:

14 C РАВНЕНИЕ АЛГОРИТМОВ ПОИСКА ПРОСТЫХ ЧИСЕЛ 14

15 А ЛГОРИТМЫ РАСПОЗНАВАНИЯ ПРОСТЫХ ЧИСЕЛ. Т ЕСТЫ ПРОСТОТЫ Тест простоты алгоритм, который по заданному натуральному числу определяет, простое ли это число. Перебор делителей Теорема Вильсона Тест Ферма Тест Пепина Тест Миллера – Рабина Тест Агравала – Каяла – Саксены 15

16 П ЕРЕБОР ДЕЛИТЕЛЕЙ Перебор делителей алгоритм тестирования простоты числа путем полного перебора всех возможных потенциальных делителей. 16 Алгоритм: 1.Перебор всех целых чисел от 2 до квадратного корня из числа n и вычисление остатка от деления n на каждое из этих чисел. 2.Если остаток от деления на некоторое число m равен нулю, то m является делителем n. В этом случае либо n объявляется составным, и алгоритм заканчивает работу. 3.По достижении квадратного корня из n и невозможности сократить n ни на одно из меньших чисел, n объявляется простым.

17 Т ЕОРЕМА В ИЛЬСОНА Теорема Вильсона теорема теории чисел, которая утверждает, что 17 p простое число тогда и только тогда, когда ( p 1)! + 1 делится на p

18 Т ЕСТ Ф ЕРМА Основан на теореме Ферма, которая гласит: 18 Для составных p истинность равенства маловероятна. Примечание:

19 Т ЕСТ П ЕПИНА 19

20 Т ЕСТ М ИЛЛЕРА — Р АБИНА Тест Миллера — Рабина — вероятностный полиномиальный тест простоты. Тест позволяет эффективно определять, является ли данное число составным. Однако, с его помощью нельзя строго доказать простоту числа. 20 Свидетели простоты и теорема Рабина Пусть m – нечетное число большее 1. Тогда m-1 представимо в виде: Целое число a, 1

21 Т ЕСТ М ИЛЛЕРА — Р АБИНА 21 Алгоритм: Параметром алгоритма Миллера – Рабина является количество раундов r. В каждом раунде выполняются следующие действия: 1.Выбирается случайное число a, 2

22 Т ЕСТ М ИЛЛЕРА — Р АБИНА Сложность алгоритма : 22 Однако, правильность работы алгоритма не всегда является доказанной. Вероятность, что составное число не будет выявлено за время t, обычно не превосходит

23 Т ЕСТ А ГРАВАЛА К АЯЛА С АКСЕНЫ ( ИЛИ ТЕСТ AKS) Универсальность : Тест AKS может использоваться для проверки простоты любых чисел. Полиномиальность : Наибольшее время работы алгоритма ограничено полиномом от количества цифр в проверяемом числе. Детерминизм : Алгоритм гарантирует получение ответа. Безусловность : Корректность теста AKS не зависит от каких-либо недоказанных гипотез. 23

24 Т ЕСТ А ГРАВАЛА К АЯЛА С АКСЕНЫ ( ИЛИ ТЕСТ AKS) Основные идеи и принципы, на котором основан алгоритм AKS: 24 Утверждение:

25 Т ЕСТ А ГРАВАЛА К АЯЛА С АКСЕНЫ ( ИЛИ ТЕСТ AKS) 25

26 Т ЕСТ А ГРАВАЛА К АЯЛА С АКСЕНЫ ( ИЛИ ТЕСТ AKS) Сложность алгоритма AKS: 26 Примечание:

Обзор алгоритмов поиска и распознавания простых чисел, информация об их применимости. Курицын Михаил Люлькова Елена Сизов Илья

Содержание Простое число Зачем искать простые числа? Алгоритмы поиска простых чисел Сравнение алгоритмов поиска простых чисел Алгоритмы распознавания простых чисел. Тесты простоты. Сравнение тестов простоты Список литературы 2

Простое число Простое число – это натуральное число, которое имеет ровно два различных натуральных делителя: единицу и самого себя. Остальные числа, кроме единицы, называются составными. Последовательность простых чисел начинается так: 2, 3, 5, 7, 11, 13, 17, 19, 23 , 29, 31, … 3

Самое большое простое число Один из рекордов поставил в своё время Эйлер, найдя простое число 231 ? 1 = 2147483647. Наибольшим известным простым числом по состоянию на февраль 2011 года является 243112609 ? 1 За нахождение простых чисел из более чем 100 000 000 и 1 000 000 000 десятичных цифр EFF назначила денежные призы соответственно в 150 000 и 250 000 долларов. 4

Зачем искать простые числа? Криптография – наука о методах обеспечения конфиденциальности (невозможности прочтения информации посторонним) и аутентичности (целостности и подлинности авторства) информации. Криптография изучает методы шифрования информации – преобразования открытого текста на основе секретного алгоритма и/или ключа в шифрованный текст. В криптографических алгоритмах одной из важных задач является проверка на простоту, т.е. умение быстро отличить просто число от составного. 5

Алгоритмы поиска простых чисел Простые способы нахождения начального списка простых чисел вплоть до некоторого значения дают : Решето Эратосфена Решето Сундарама Решето Аткина 6

7 Решето Эратосфена Алгоритм: Пусть p = 2 (первому простому числу). Считая от р, шагами по р, зачеркнуть в списке все числа от 2р до n. Найти первое не зачеркнутое число, большее чем p, и присвоить значение переменной p это число. Повторять шаги 3 и 4 до тех пор, пока p не станет больше чем n. Простые числа: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.

Читайте также:  Информатика клавиатура назначение клавиш

Решето Эратосфена Сложность алгоритма: 8 O( n? . 2 . 2 (??))

Решето Сундарама 9 Алгоритм: Из ряда натуральных чисел от 1 до N исключаются все числа вида i + j + 2ij ( i = 1,2, ,…, 2??+1 ?1 2 ; j = i,i+1,…, . 2??+1 ). Каждое из оставшихся чисел умножается на 2 и увеличивается на 1. Полученная в результате последовательность представляет собой все нечётные простые числа в отрезке [1,2N+1]. i = 1, j = 1,…,6; i = 2, j = 1,2,3; Простые числа: 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41.

Решето Сундарама. Обоснование Алгоритм работает с нечётными натуральными числами большими 1, представленными в виде 2m+1, где m является натуральным числом. Если число 2m+1 является составным, то оно представляется в виде произведения двух нечётных чисел больших единицы, то есть: 10 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 не будет исключено в процессе работы алгоритма.

Решето Аткина B основу алгоритма "решета Аткина" положены три стандартные теоремы теории элементарных чисел: 11 n – простое, если: 4? ?? 2 + ?? 2 =?? (??>0, ??>0) n mod 4 = 1 n – нечетное число n – простое, если: 3? ?? 2 + ?? 2 =?? (??>0, ??>0) n mod 6 = 1 n – нечетное число n – простое, если: 3? ?? 2 ? ?? 2 =?? (??>0, ??>0) n mod 12 = 11 n – нечетное число 1. 2. 3.

Алгоритм Создать решето (массив соответствия простым числам для всех положительных, целых чисел начиная с 2). Изначально все элементы решета помечаются как составные. Для каждого числа n в решете , если остаток от деления по модулю 60: Равен 1, 13, 17, 29, 37, 41, 49, или 53, и n = 4 * x2 + y2 поменять значение в решете на противоположное. Равен 7, 19, 31, или 43, и n = 3 * x2 + y2; поменять значение решете на противоположное. Равен 11, 23, 47, или 59, и n = 3 * x2 — y2 при(x > y); поменять значение в решете на противоположное. (х и у целые, положительные числа) Взять наименьшее число из решета, помеченное как простое, и пометить все элементы решета, кратные квадрату этого простого числа как составные. Повторить шаг 3 12

Решето Аткина Алгоритм имеет асимптотическую сложность: 13 ??( ?? log log ?? ) и требует следующее кол-во бит памяти: O ( ?? 1 2 +??(1) )

Cравнение алгоритмов поиска простых чисел 14

Алгоритмы распознавания простых чисел. Тесты простоты Тест простоты — алгоритм, который по заданному натуральному числу определяет, простое ли это число. Перебор делителей Теорема Вильсона Тест Ферма Тест Пепина Тест Миллера – Рабина Тест Агравала – Каяла – Саксены 15

Перебор делителей Перебор делителей — алгоритм тестирования простоты числа путем полного перебора всех возможных потенциальных делителей. 16 Алгоритм: Перебор всех целых чисел от 2 до квадратного корня из числа n и вычисление остатка от деления n на каждое из этих чисел. Если остаток от деления на некоторое число m равен нулю, то m является делителем n. В этом случае либо n объявляется составным, и алгоритм заканчивает работу. По достижении квадратного корня из n и невозможности сократить n ни на одно из меньших чисел, n объявляется простым.

Теорема Вильсона Теорема Вильсона — теорема теории чисел, которая утверждает, что 17 p — простое число тогда и только тогда, когда (p ? 1)! + 1 делится на p

Тест Ферма Основан на теореме Ферма, которая гласит: 18 Если p – простое число, то для любого целого a выполняется равенство ?? . 1 ?1(. ??) или ( ?? . 1 ?1) делится на ?? нацело. Для составных p истинность равенства маловероятна. Примечание:

Тест Пепина Тест пепина является тестом простоты для чисел Ферма. Число ферма – это число вида: ?? ?? = 2 2 ?? +1, ?? – целое, неотрицательное. Число Ферма является простым тогда и только тогда, когда ?? ( ?? ?? . )/?? . (. ?? ?? ). На сегодняшний день известно только 5 простых чисел Ферма: 3, 5, 17, 257 и 65537. 19

Тест Миллера — Рабина Тест Миллера — Рабина — вероятностный полиномиальный тест простоты. Тест позволяет эффективно определять, является ли данное число составным. Однако, с его помощью нельзя строго доказать простоту числа. 20 Свидетели простоты и теорема Рабина Пусть m – нечетное число большее 1. Тогда m-1 представимо в виде: m-1 = 2 ?? *t , где t – нечетно Целое число a, 1

Тест Миллера — Рабина 21 Алгоритм: Параметром алгоритма Миллера – Рабина является количество раундов r. В каждом раунде выполняются следующие действия: Выбирается случайное число a, 2 2 < ?? – наибольший простой делитель у (. 1); . ?? ?4 ?? . 2 ?? . ( ?? . 1 ?? ?1(. ??))) . ; >?? = ??+1; > . ?? = 1 . ( 2 ?? . 2 ?? +1) . . ?? ? ?? ?? . . ?? ?? ?1. вернуть составное; . ?? = ?? ?? ;. ?целые;. 2 вернуть составное; вернуть простое; 25

Тест Агравала — Каяла — Саксены ( или тест AKS) Сложность алгоритма AKS: 26 O ( . 19 ??) Примечание: Выражение: . ?? ? ?? ?? . . ?? ?? ?1. означает следующее: для многочленов (. ) ?? и ?? ?? . найдется многочлен ?? ?? . ?? (кольцо многочленов от x с целыми коэффициентами) такой, что все коэффициенты многочлена (. ) ?? ? ?? ?? . ? ?? ?? ?1 . ?? кратны .