Quais divisores devem ser testados para verificar se um inteiro n>1 é primo?

Testar divisibilidade apenas pelos números primos menores ou iguais a \( \sqrt{n} \).

Explicação:
Se \(n\) tiver um divisor composto, ele pode ser escrito como \(a\cdot b=n\) com \(a\le b\), logo \(a\le\sqrt{n}\). Portanto, se não houver nenhum divisor primo ≤ \( \sqrt{n} \), não existirá fator não trivial, e \(n\) é primo.

Exemplo:
Verificar \(n=91\).
\( \sqrt{91}\approx 9{,}54\), logo testar primos \(2,3,5,7\).
\(91\mod 2=1,\;91\mod 3=1,\;91\mod 5=1,\;91\mod 7=0\).
Como \(91\mod 7=0\), 91 não é primo.