Критерии простоты чисел специального вида. Простые числа Мерсенна, тест Люка-Лемера.
Функция Array [f, 100000, 4] генерирует следующий список из 100000 элементов {f[4], f[5],…} – Функция DeleteCases [Array [f,100000, 4],Null] удаляет из него элементы, равные Null. Затем функция Sort сортирует этот список, а функция Union рассматривает его как множество и тем самым исключает из него повторяющиеся элементы.
Из массива, который первоначально содержал сто элементов, получается список всего из 15 элементов.
tl=Union[Sort[DeleteCases[Array[f,100.4],Null]]] {3.5.7.11.23.29.37.43.73.83.131.179.191.239.251}Понятно, что это очень мало. Но даже если бы мы исходили из тысячи простых чисел, у нас бы получился список из 80 элементов.
Если же взять сто тысяч простых чисел, получится список из 4536 элементов. Конечно, это тоже не очень много. Кроме того, не все элементы этого списка годятся для отсеивания. Не годятся, например, р = 3, 5, 7. Ведь если простое число р попало в нашу таблицу, это означает лишь, что М р делится на некоторое простое число, возможно на себя, – и тогда оно является простым числом! Поэтому для отсеивания пригодны лишь те элементы нашей таблицы, для которых Л/ больше самого большого простого модуля q, использованного для построения нашей таблицы. Правда, число Мерсенна Мр растет гораздо быстрее, чем л-е простое число рп. Поэтому для большинства элементов из полученного списка выполняется неравенство Мр >q, где q – самый большой простой модуль, использованный для построения нашей таблицы.
Однако проблема заключается в том, что в нашей таблице слишком мало чисел. Даже если для построения таблицы мы используем миллион простых чисел, таблица будет содержать всего лишь 37330 чисел. Это значит, что с помощью такой таблицы мы сможем отбраковать менее 4% чисел. Соответственно, и быстродействие программы мы повысим менее, чем на 4%. Так что в данном случае усложнение программы не оправдано, потому что для большинства чисел (более 96%) будет применяться критерий Люка-Лемера.
Но оказывается, эффективные критерии простоты существуют не только для чисел Мерсенна! Эффективные критерии существуют, например, и для чисел вида k-2n +1.