Verificação de Número Primo

Problema

Um número primo é maior que 1 e divisível apenas por 1 e por ele mesmo. Verificar divisores até a raiz quadrada de n é suficiente.

Implemente is_prime(n).

n: O número a ser testado.

Retorne true se n for primo, caso contrário retorne false.

-1.000 ≤ n ≤ 1.000.000.000.000

Exemplo 1

Entrada:
n = 29

Saída esperada:
expected = True

Entrada:
long long n = 29;

Saída esperada:
bool expected = true;

Entrada:
long n = 29;

Saída esperada:
bool expected = true;

29 não possui divisores além de 1 e 29.

Exemplo 2

Entrada:
n = 21

Saída esperada:
expected = False

Entrada:
long long n = 21;

Saída esperada:
bool expected = false;

Entrada:
long n = 21;

Saída esperada:
bool expected = false;

21 = 3 × 7, portanto não é primo.

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

Trate primeiro os números abaixo de 2; eles não podem ser primos.

Dica 2

Teste possíveis divisores só até a raiz quadrada do número.

Dica 3

Cuidado com números pares e fatores repetidos; um divisor já basta para descartar a primalidade.

Complexidade esperada

tempo O(sqrt(n)), espaço extra O(1)

Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.