[Из песочницы] Алгоритм проверки на простоту за O (log N)
Проверка на простоту Чтобы определить, является ли данное число N простым, безусловно, достаточно написать простой цикл поиска делителей числа N: bool prime (long long n){ for (long long i=2; i<=sqrt(n);i++) if(n%i==0) return false; return true; } Данная функция проверки числа на простоту достаточно эффективна — асимптотика ее работы O (sqrt(N)). Однако, иногда в спортивном программировании нужно уметь проверять число на простоту быстрее. В некоторых случаях, когда требуется выполнять такую проверку для чисел из некоторого диапазона, то целесообразно воспользоваться алгоритмом Решето Эратосфена. В данной статье я рассмотрю другой способ выполнять единичные проверки на простоту — тест Ферма.Читать дальше →
