समस्या
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.
सीमाएँ
-1,000 ≤ n ≤ 1,000,000,000,000
उदाहरण
उदाहरण 1
इनपुट:
n = 29
अपेक्षित आउटपुट:
expected = Trueइनपुट:
long long n = 29;
अपेक्षित आउटपुट:
bool expected = true;इनपुट:
long n = 29;
अपेक्षित आउटपुट:
bool expected = true;व्याख्या
29 has no divisors other than 1 and 29.
उदाहरण 2
इनपुट:
n = 21
अपेक्षित आउटपुट:
expected = Falseइनपुट:
long long n = 21;
अपेक्षित आउटपुट:
bool expected = false;इनपुट:
long n = 21;
अपेक्षित आउटपुट:
bool expected = false;व्याख्या
21 = 3 × 7, so it is not prime.
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
Handle numbers below 2 first; they cannot be prime.
संकेत 2
Test possible divisors only up to the square root of the number.
संकेत 3
Watch out for even numbers and repeated factors, since one divisor is enough to disqualify primality.
अपेक्षित जटिलता
O(sqrt(n)) time, O(1) extra space
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।