Complexity: $O(k * (\log{n})^3)$, где k – число проверок числа p.

https://ru.wikipedia.org/wiki/Тест_Миллера_—_Рабина

На практике тест Миллера-Рабина реализуется следующим образом:

1. Дано $p$, нужно найти $s$, такое что $p - 1 = 2^s*q$ для некоторого нечетного $q$.
2. Возьмем случайное $a \in \{1, ..., p-1\}$
3. Если $a^{p-1} \space == 1 \space mod \space p$, то $p$ простое и мы прекращаем выполнение (в жизни прекращаем выполнение, в контесте нам нужно проверить ещё пункт 4 🙂).
4. Для $r = \{0, ..., s-1\}$ проверить равенство $a^{2^r * q} = -1 \space mod \space p$. Если равенство выполняется, то $p$ простое (прекращаем выполнение)
5. Если ни одно из вышеприведенных условий не выполнено, то $p$ – составное.