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).
Input
n: The number to test.
Output
Return true if n is prime, otherwise false.
Vincoli
-1,000 ≤ n ≤ 1,000,000,000,000
Esempi
Esempio 1
Input:
n = 29
Output atteso:
expected = TrueInput:
long long n = 29;
Output atteso:
bool expected = true;Input:
long n = 29;
Output atteso:
bool expected = true;Spiegazione
29 has no divisors other than 1 and 29.
Esempio 2
Input:
n = 21
Output atteso:
expected = FalseInput:
long long n = 21;
Output atteso:
bool expected = false;Input:
long n = 21;
Output atteso:
bool expected = false;Spiegazione
21 = 3 × 7, so it is not prime.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Handle numbers below 2 first; they cannot be prime.
Suggerimento 2
Test possible divisors only up to the square root of the number.
Suggerimento 3
Watch out for even numbers and repeated factors, since one divisor is enough to disqualify primality.
Complessità attesa
O(sqrt(n)) time, O(1) extra space
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.