второй этап теста:
(2^n) mod n = 2
Как понимаю это переформулировка
малой теоремы Ферма об простоте чисел по основанию 2 (
числа Пуле). Для них в сети есть
полный список всех исключений до ![$2^{64}\approx1.84\cdot10^{19}$ $2^{64}\approx1.84\cdot10^{19}$](https://dxdy-03.korotkov.co.uk/f/6/5/8/658cd0f2be148ad2722ed43366a9fb8982.png)
, все остальные составные им определяются правильно, потому нет нужды проверять все числа подряд, достаточно проверить только эти 119млн чисел по первому критерию. До
![$10^{12}$ $10^{12}$](https://dxdy-02.korotkov.co.uk/f/1/8/6/186996cc836533ab0601d8a580cf784782.png)
список из сотни тысяч чисел есть и в
A001567 (а среди ссылок есть и первый список), тоже достаточно проверить лишь их по первому критерию.
-- 18.07.2024, 15:50 --Плюс за счёт очень небольшого усложнения второго критерия (причём нередко даже с увеличением скорости проверки) можно уменьшить количество исключений почти вчетверо, с 119млн до 32млн -
сильные псевдопростые и
A001262 (первые 10000 штук). И их тоже есть
полный список исключений до ![$2^{64}\approx 1.84\cdot10^{19}$ $2^{64}\approx 1.84\cdot10^{19}$](https://dxdy-01.korotkov.co.uk/f/8/8/9/8894b0ddc8ebd02aafbdb754e4ae967a82.png)
, только которые и достаточно проверить по первому критерию.
-- 18.07.2024, 15:53 --А первый критерий очень похож на
псевдопростые Фибоначчи.
Так что ничего нового похоже в таком тесте нет.