Отправляет email-рассылки с помощью сервиса Sendsay

Всё о работе в Интернет

Подписаться Бесплатная «Серебряная» новостная рассылка Подписчиков 7.350 RSS
←   Январь 2010   →
 1
 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
31


За последние 60 дней 1 выпусков (1 раз в 2 месяца)


Сайт рассылки: http://bestinvestblog.com
Открыта: 10-02-2009

Автор
bestinvestblog

Статистика

7.350 подписчиков
0 за неделю
←   Все выпуски   →

Занятие 60. Алгоритм и подпрограмма определения, является ли заданное натуральное число простым.


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

Учитель:

- Тема сегодняшнего урока – “Простые числа”.

Весь класс:

- У-у-у...

Учитель:

- Hу, ладно, ладно, в конце немного потанцуем, послушаем музыку.

ПРОСТЫЕ ЧИСЛА

Элементарная математика определяет простые числа следующим образом:

-       все натуральные числа, кроме 1, имеют, по меньшей мере, двух делителей – единицу и самого себя;

-       те из них, которые не имеют никаких других делителей, называются простыми; например, несколько первых простых чисел 2, 3, 5, 7, 11, 13, 17, 19;

-       те числа, которые имеют ещё и других делителей, называются составными; например, 12 – составное число (его делители 1, 2, 3, 4, 6, 12);

-       число 1 выделяют особо, не относя ни к простым, ни к составным; это связано с тем, что для единицы не имеют силы многие правила, справедливые для всех остальных простых чисел.

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

Алгоритм C.2.6 “Простое число”, который мы с вами сегодня рассмотрим, не претендует на наличие у него каких-то супервозможностей. Дело в том, что его применения будут ограничены компьютерным представлением целых чисел. А это, как известно, при программировании на Паскале диктует возможность использования только таких целых чисел, значения которых не выходят за пределы длинного целого типа LongInt. Наибольшее допустимое целое число составляет при этом 2147483647, что далеко не удовлетворяет потребности криптографии.

Но, как поётся в известной песне, “всё ещё впереди…”. Итак…

Задача C.2.6. “Простое число”. Построить подпрограмму, определяющую, является ли простым заданное натуральное число Q > 1.

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

алг Простое ( Q: нат ): лог

нач

Простое := Количество_делителей (Q) = 2

кон

Значение приведённой алгоритм-функции будет истинным, если число Q является простым. Здесь использован вспомогательный алгоритм подсчёта количества делителей, построенный на базе материала предыдущего занятия.

алг Количество_делителей ( Q: нат ): нат

нач k, D: нат

k := 2

для D от 2 до Sqrt(Q)

выполнять если Q mod D = 0 то k := k + 2

если Точный_квадрат (Q) то k := k – 1

Количество_делителей := k

кон

А вот теперь задумаемся над тем, нужно ли нам знать точное количество делителей, чтобы сделать правильный вывод о том, является ли данное число Q простым?

Очевидно, для решения задачи вполне достаточно было бы выяснить, равно или не равно 2 количество делителей данного числа Q. Или, что ещё эффективнее, выяснить, имеются ли ещё и другие делители на промежутке от 2 до Sqrt(Q). В последнем случае следует поочерёдно проверять возможные делители, начиная с 2, и делать это, пока, во-первых, не будет обнаружен ещё какой-то делитель, и, во-вторых, пока не будут исчерпаны сами возможные делители. Иными словами говоря, процесс поиска делителя должен быть прекращён или в момент обнаружения этого делителя, или в момент исчерпания всех возможных делителей из промежутка от 2 до Sqrt(Q). Такой подход к построению алгоритма может быть реализован на основе использования цикла с предусловием пока... . При этом вполне очевидно, что за счёт этого быстродействие его станет ещё выше. Проявляться это будет на числах, не являющихся простыми. Например, для выяснения того, что число 102 не является простым, достаточно будет проверить всего один делитель 2, в случае Q = 105 достаточно будет проверить двух делителей (2 и 3) и т. д. 

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

Найден := НЕТ; D := 2

пока не Найден и (D*D <= Q) 

выполнять нс  Найден := Q mod D = 0; D := D + 1 кс

Простое := не Найден

В приведённом фрагменте алгоритма переменная D имеет тот же смысл, что и ранее. Значения D – это значения потенциальных делителей числа Q. Начальное значение D := 2 устанавливается перед циклом. Перед каждым очередным  исполнением цикла осуществляется проверка, не выходит ли значение D за допустимые пределы. При этом используется условие D*D <= Q, что, очевидно, эффективнее условия D <= Sqrt(Q). В самом цикле на каждом шаге осуществляется увеличение D на единицу. Так организован в цикле процесс просмотра возможных делителей числа Q.

Проверка возможных делителей числа Q осуществляется с помощью логической переменной Найден. Ранее вместо неё использовалась переменная k, которая выполняла роль счётчика делителей. Теперь переменная Найден выполняет роль флажка, сигнализирующего о наличии делителя в промежутке от 2 до Sqrt(Q). Если условие Q mod D = 0 истинно, то переменная Найден принимает значение ДА, и это означает, что делитель найден. Соответственно перед циклом установлено начальное значение Найден := НЕТ (делитель ещё не найден). Проверка условия не Найден (пока делитель не найден) осуществляется в цикле. Как только делитель будет найден (переменная Найден станет истинной, выражение не Найден станет ложным), цикл будет прекращён.

Естественно, значение результата Простое противоположно по смыслу  значению переменной Найден.

Теперь поставим ещё один вопрос. Сколько нужно просмотреть потенциальных чётных делителей данного числа Q, чтобы сделать вывод об отсутствии у него чётных делителеё вообще? Ответ ясен. Чтобы выяснить, не имеет ли число Q чётных делителей, достаточно проверить, не является ли оно чётным само, то есть не имеет ли оно делителя, равного 2. Действительно, если число Q = 101 не делится без остатка на 2 (а это действительно так), то остальные чётные делители (в данном случае 4, 6, 8 и 10) можно не проверять вообще.

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

Итак, мы решили учитывать в циклическом процессе проверки  только нечётные делители. Поэтому для переменной D перед циклом мы должны устанавливать начальное значение D := 3, а в самом цикле на каждом шаге увеличивать её значение на 2, то есть D := D + 2.

Возможный делитель D = 2 придётся проверить отдельно. Лучше всего это сделать перед циклом с помощью переменной Найден, а именно: Найден := Q mod 2 = 0. Получаем такой вариант алгоритма:

Найден := Q mod 2 = 0; D := 3

пока не Найден и (D*D <= Q) 

выполнять нс  Найден := Q mod D = 0; D := D + 2 кс

Простое := не Найден

Таким образом, если данное число Q – чётно, то делитель, равный 2, будет обнаружен непосредственно перед циклом (переменная Найден примет значение ДА). Поэтому и цикл не будет выполняться (не Найден = НЕТ), и правильный результат будет получен сразу же.

Единственная неприятность заключается в том, что в таком виде алгоритм теряет работоспособность при Q = 2. Это единственное простое число, которое является чётным. Беде можно помочь, если случай Q = 2 исключить из процесса какой бы то ни было проверки вообще, и устанавливать при этом правильное значение результата принудительно. Это можно сделать, например, следующим образом: Простое := не Найден или (Q = 2). Таким образом, окончательный вариант алгоритма приобретает вид:

Найден := Q mod 2 = 0; D := 3

пока не Найден и (D*D <= Q) 

выполнять нс  Найден := Q mod D = 0; D := D + 2 кс

Простое := не Найден или (Q = 2)

В данном варианте алгоритма цикл не будет использоваться вообще не только при чётных Q, но и при всех Q < 9. Действительно, поскольку возможные делители начинаются с D = 3, то условие D*D <= Q будет при этом ложным. Результат будет зависеть исключительно от того, чётно или нечётно число Q, а также от того, не равняется ли оно двум (2, 3, 5 и 7 – простые числа, 4, 6 и 8 – составные).

На языке Паскаль окончательный результат решения поставленной задачи выглядит следующим образом:

   Function Prime_Number ( Q: LongInt ): Boolean;
      Var D: LongInt; Find: Boolean;
   Begin
      Find := Q Mod 2 = 0; D := 3;
      While Not Find And (D*D <= Q) Do
         Begin Find := Q Mod D = 0; D := D + 2 End;
      Prime_Number := Not Find Or (Q = 2)
   End;

Подпрограмма была протестирована на наибольшем простом числе 2147302891, находящемся в пределах типа LongInt.

Уважаемые подписчики! При необходимости задать вопрос, проконсультироваться, уточнить или обсудить что-либо обращайтесь через Гостевую книгу моего персонального сайта http://a-morgun.narod.ru. При этом настоятельно рекомендую пользоваться браузером Internet Explorer.

С уважением, Александр.

 
В избранное