Prime Number Check

Problema

A prime number is greater than 1 and divisible only by 1 and itself. Checking divisors up to the square root of n is enough.

Implement is_prime(n).

n: The number to test.

Return true if n is prime, otherwise false.

-1,000 ≤ n ≤ 1,000,000,000,000

Ejemplo 1

Entrada:
n = 29

Salida esperada:
expected = True

Entrada:
long long n = 29;

Salida esperada:
bool expected = true;

Entrada:
long n = 29;

Salida esperada:
bool expected = true;

29 has no divisors other than 1 and 29.

Ejemplo 2

Entrada:
n = 21

Salida esperada:
expected = False

Entrada:
long long n = 21;

Salida esperada:
bool expected = false;

Entrada:
long n = 21;

Salida esperada:
bool expected = false;

21 = 3 × 7, so it is not prime.

Inténtalo primero por tu cuenta y luego abre las pistas una a una.

Pista 1

Handle numbers below 2 first; they cannot be prime.

Pista 2

Test possible divisors only up to the square root of the number.

Pista 3

Watch out for even numbers and repeated factors, since one divisor is enough to disqualify primality.

Complejidad esperada

O(sqrt(n)) time, O(1) extra space

Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.