किसी संख्या की अभाज्यता की जांच – थोड़ा तेज़
मान लीजिए कि एक प्रोग्राम, जो किसी संख्या की अभाज्यता (prime) की जांच करता है, किसी बड़ी कंपनी में उत्पादन स्तर पर उपयोग हो रहा है। अब, जैसे-जैसे कंपनी तेजी से बढ़ती है और उपयोगकर्ताओं की संख्या में इज़ाफा होता जाता है, वैसे-वैसे आपके कोड को भेजे जाने वाले अनुरोध भी बढ़ जाते हैं। कंपनी आपसे इस कोड को अनुकूलित (optimize) करने और इसे थोड़ा तेज़ बनाने के लिए कहती है, ताकि आने वाले ढेर सारे नए उपयोगकर्ताओं का भार संभाला जा सके।
आपका पिछला समाधान संभवतः इस प्रकार था:
- 2 से
nतक के सभी मानों पर लूप करके, सभी विभाजकों की गिनती करना।
- 2 से
nतक के मानों पर लूप करके, जहां भी कोई विभाजक मिलता, वहीं रुक जाना।
इस प्रक्रिया को बेहतर बनाने के लिए हम कुछ छोटे-छोटे बदलाव कर सकते हैं:
Optimization 1:
2 से
n तक सभी मानों को जांचने की बजाय, पहले जांच लें कि n को 2 से विभाजित किया जा सकता है या नहीं। अगर n को 2 से विभाजित नहीं किया जा सकता, तो फिर बड़ी सम संख्याओं (4, 6, 8, 10, 12 आदि) को जांचने की ज़रूरत नहीं रह जाती, क्योंकि अगर 2 से विभाज्य नहीं है तो अन्य सम संख्याओं से भी विभाज्य नहीं होगा।Optimization 2:
2 से
n तक लूप करने की बजाय, 2 से n/2 तक ही लूप करें, क्योंकि 2 सबसे छोटा संभावित विभाजक है ⇒ n/2 से बड़े किसी मान से विभाजक मिलना संभव नहीं होता।हम इन दोनों अनुकूलनों (optimizations) को मिलाकर इस्तेमाल कर सकते हैं। इस तरह 2 के बाद सिर्फ विषम संख्याओं को
n/2 तक जांचना होगा। इस तरह लगभग n/4 संख्याओं की जांच होती है, यानी साधारण रेखीय जांच की तुलना में कोड लगभग चार गुना तेज़ हो जाता है।ये अनुकूलन कोड को थोड़ा तेज़ तो बना देते हैं, लेकिन जटिलता (complexity) के लिहाज़ से एल्गोरिद्म अभी भी विभाजकों की रेखीय खोज ही करता है। यानी जैसे-जैसे
n बढ़ता है, एल्गोरिद्म द्वारा किए जाने वाले काम की मात्रा भी उसी अनुपात में बढ़ती जाती है। हम आगे देखेंगे कि अभाज्यता की जांच को कैसे बड़े पैमाने पर अनुकूलित किया जा सकता है, ताकि यह n के बढ़ने के अनुपात में काम न बढ़ाए।Input
इनपुट की पहली पंक्ति में एकल पूर्णांक
n (1 ≤ n ≤ ) दिया हुआ है।Output
यदि
n अभाज्य है, तो प्रोग्राम को Yes प्रिंट करना चाहिए, अन्यथा No प्रिंट करना चाहिए।Examples
Input | Output |
8 | No |
7 | Yes |
1 | No |
19 | Yes |
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB