Dado o número natural A, para testar se A é primo se fazem testes para saber se determinados números são divisíveis por A. Marque a alternativa que apresenta a menor quantidade pos

Gabarito

D

Comentário do professor

A alternativa diz para testar se A é divisível por todos os números primos menores que a raiz quadrada de A. Isso funciona porque, se A for composto, existe uma fatoração \(A=x\cdot y\) com \(1

O número \(x\) tem um divisor primo \(p\) tal que \(p\le x\le\sqrt{A}\). Como \(p\) divide \(x\) e \(x\) divide \(A\), temos \(p\) divide \(A\). Portanto basta testar os primos até \(\sqrt{A}\) para encontrar esse divisor.

Testar apenas primos é mais eficiente que testar todos os inteiros menores que \(\sqrt{A}\), porque qualquer divisor não primo contém um divisor primo que já será testado.

Se nenhum desses primos divide A e \(A>1\), então A é primo. Lembre-se de tratar o caso \(A=1\) separadamente, pois 1 não é primo.