Если же взять сто тысяч
Пример 1
Если же взять сто тысяч простых чисел, получится список из 4536 элементов. Конечно, это тоже не очень много. Кроме того, не все элементы этого списка годятся для отсеивания. Не годятся, например, р = 3, 5, 7. Ведь если простое число р попало в нашу таблицу, это означает лишь, что М р делится на некоторое простое число, возможно на себя, — и тогда оно является простым числом! Поэтому для отсеивания пригодны лишь те элементы нашей таблицы, для которых Л/ больше самого большого простого модуля q, использованного для построения нашей таблицы. Правда, число Мерсенна Мр растет гораздо быстрее, чем л-е простое число рп. Поэтому для большинства элементов из полученного списка выполняется неравенство Мр >q, где q — самый большой простой модуль, использованный для построения нашей таблицы. Однако проблема заключается в том, что в нашей таблице слишком мало чисел. Даже если для построения таблицы мы используем миллион простых чисел, таблица будет содержать всего лишь 37330 чисел. Это значит, что с помощью такой таблицы мы сможем отбраковать менее 4% чисел. Соответственно, и быстродействие программы мы повысим менее, чем на 4 %. Так что в данном случае усложнение программы не оправдано, потому что для большинства чисел (более 96%) будет применяться критерий Люка-Лемера.
Но оказывается, эффективные критерии простоты существуют не только для чисел Мерсенна! Эффективные критерии существуют, например, и для чисел вида k-2n +1.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий