समस्या
मूल संख्या वह होती है जो 1 से बड़ी हो और केवल 1 तथा स्वयं से ही विभाजित हो सके। किसी संख्या n के लिए उसके वर्गमूल तक के भाजकों की जांच करना पर्याप्त है।
is_prime(n) को लागू करें।
इनपुट
n: जांचने के लिए संख्या।
आउटपुट
यदि n मूल है तो true लौटाएँ, अन्यथा false लौटाएँ।
सीमाएँ
-1,000 ≤ n ≤ 1,000,000,000,000
उदाहरण
इनपुट:
n = 29
अपेक्षित आउटपुट:
expected = Trueइनपुट:
long long n = 29;
अपेक्षित आउटपुट:
bool expected = true;इनपुट:
long n = 29;
अपेक्षित आउटपुट:
bool expected = true;व्याख्या
29 के अलावा 1 और 29 के कोई अन्य भाजक नहीं हैं।
इनपुट:
n = 21
अपेक्षित आउटपुट:
expected = Falseइनपुट:
long long n = 21;
अपेक्षित आउटपुट:
bool expected = false;इनपुट:
long n = 21;
अपेक्षित आउटपुट:
bool expected = false;व्याख्या
21 = 3 × 7, इसलिए यह मूल संख्या नहीं है।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
2 से छोटे numbers को पहले handle करें; वे prime नहीं हो सकते.
संकेत 2
Possible divisors को सिर्फ number के square root तक test करें.
संकेत 3
Even numbers और repeated factors पर ध्यान दें, क्योंकि एक divisor ही primality को disqualify करने के लिए काफी है.
अपेक्षित जटिलता
समय O(sqrt(n)), अतिरिक्त स्थान O(1)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।