yourdomain.com

1242687 1. Простите, не понимаю. Если тест не принял число за составное - то оно считается простым, разве нет? Если оно на самом деле составное, то и моё и Ваше утверждение эквивалентны. А если простое - то тест и не ошибся. Это я запутался в терминологии, прошу прощения. Я имел в виду strong pseud...

1242685 Третье же предложение по указанной Вами ссылке "Однако, с его помощью нельзя строго доказать простоту числа." - т.е. можно доказать что число составное, но вот что оно простое - не доказать. Это и можно назвать "псевдопростотой", т.е. скорее всего простое, но ... Если бы...

1242678 1242671 И для каждого теста существуют "псевдопростые" числа, на которых он гарантированно ошибается... Примеры приведите, пожалуйста. Голословные заявления ничего не доказывают. Псевдопростое число . Для (вероятностного) теста Миллера-Рабина не существует псевдопростых чисел. Это...

1242642 AKS-тест работает за $$O(\ln^6 n)$$ . Для проверки $$k$$ подряд идущих чисел длины $$n$$ достаточно $$O(k\ln^6 n)$$ операций. Решето проверяет $$k$$ подряд идущих чисел за $$O(k^2)+O(k(1-1/2)(1-1/3)...(1-1/p)\sqrt{n})=O(k^2)+O&...