किसी संख्या के प्राइम (अभाज्य) होने की तेज़ जाँच
अब तक, किसी संख्या
n के प्राइम (अभाज्य) होने या न होने का पता लगाने के लिए मूलतः एक रेखीय खोज (linear search) द्वारा भाजकों की जाँच की जा रही थी। इसका मतलब है कि यदि हम n को बड़ा करते हैं, तो n के प्राइम होने की जाँच के लिए किए जाने वाले ऑपरेशनों की संख्या समानुपाती (proportional) रूप से बढ़ती जाती है (किसी नियत गुणांक के साथ)। इसलिए, यदि हम सबसे ख़राब स्थितियों पर विचार करें (वे सभी स्थितियाँ जिनमें n एक प्राइम संख्या होती है, जैसे 51, 107 इत्यादि) – तो हमारे एल्गोरिद्म को n को जाँचने में लगभग n/4 ऑपरेशनों की ज़रूरत होती है।इसका मतलब यह है कि अगर हम
n को 10 गुना बढ़ाते हैं, तो एल्गोरिद्म 10 गुना अधिक ऑपरेशन करेगा। अगर हम n को 100 गुना बढ़ाते हैं, तो एल्गोरिद्म 100 गुना अधिक ऑपरेशन करेगा। यह दर्शाता है कि हमारा एल्गोरिद्म n के समानुपाती प्रदर्शन दे रहा है। क्या इसे और तेज़ी से करना संभव है? ऐसा लगता है कि अब भी बहुत-सी अनावश्यक जाँच हो रही है।The तरीका:
मान लीजिए संख्या
n का कोई भाजक d है।इसका मतलब है कि
n, d पर विभाज्य (divisible) है और दोनों d तथा पूर्णांक हैं। साथ ही, या तो d या फिर में से कोई एक से कम या उसके बराबर होगा। अतः जब हम किसी संख्या को प्राइम मानना चाहते हैं, तो हमें तक ही लूप चलाना काफ़ी है— तक जाने की आवश्यकता नहीं। हमें सिर्फ़ यह देखना है कि कोई संख्या 1 और स्वयं n के अलावा किसी अन्य संख्या से विभाज्य है या नहीं, तो हम d या में से जो भी छोटा है, उसकी परख करना पर्याप्त समझते हैं। चूँकि उन दोनों में से एक से छोटा ही होगा, इसलिए हम तक जाँच करके रुक सकते हैं।यह वाकई एक बड़ा सुधार है!
n की बजाय ऑपरेशन करना बहुत बड़ा अंतर लाता है। कल्पना कीजिए कि कोई एल्गोरिद्म किसी गणना को पूरा करने में 10 साल (3650 दिन) लगाता। अगर वही एल्गोरिद्म अब ऑपरेशन के सिद्धांत पर काम करने लगे, तो उसे वही काम करने में केवल 2 महीने (61 दिन) लगेंगे।क्या किसी संख्या के प्राइम होने की जाँच के बेहतर एल्गोरिद्म भी हैं?
हाँ! आप इनके बारे में Algorithms for Competitive Programming पर और अधिक पढ़ सकते हैं। ऐसे एल्गोरिद्म हैं, जिनकी जटिलता
n बढ़ने पर से भी धीमी दर (जैसे लोगैरिथमिक) से बढ़ती है।इनपुट
इनपुट की पहली पंक्ति में एक एकल पूर्णांक
n दिया जाता है (1 ≤ n ≤ )।आउटपुट
यदि
n प्राइम है, तो प्रोग्राम को Yes प्रिंट करना चाहिए; अन्यथा No प्रिंट करना चाहिए।Examples
Input | Output |
1 | No |
11 | Yes |
353557 | Yes |
34134741 | No |
902468477 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB