Problème
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).
Input
n: The number to test.
Output
Return true if n is prime, otherwise false.
Contraintes
-1,000 ≤ n ≤ 1,000,000,000,000
Exemples
Exemple 1
Entrée :
n = 29
Sortie attendue :
expected = TrueEntrée :
long long n = 29;
Sortie attendue :
bool expected = true;Entrée :
long n = 29;
Sortie attendue :
bool expected = true;Explication
29 has no divisors other than 1 and 29.
Exemple 2
Entrée :
n = 21
Sortie attendue :
expected = FalseEntrée :
long long n = 21;
Sortie attendue :
bool expected = false;Entrée :
long n = 21;
Sortie attendue :
bool expected = false;Explication
21 = 3 × 7, so it is not prime.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Handle numbers below 2 first; they cannot be prime.
Indice 2
Test possible divisors only up to the square root of the number.
Indice 3
Watch out for even numbers and repeated factors, since one divisor is enough to disqualify primality.
Complexité attendue
O(sqrt(n)) time, O(1) extra space
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.