संख्यात्मक एल्गोरिदम

भाजक और अभाज्य संख्याएँ

परीक्षण-विभाजन

पूर्णांक $n \geq 2$ अभाज्य है यदि उसके एकमात्र धनात्मक भाजक 1 और $n$ हों; यदि उसका कोई और भाजक हो, तो वह संयुक्त है; 0 और 1 न यह हैं न वह। परिभाषा तुरंत एक एल्गोरिदम सुझाती है: हर उम्मीदवार $d$ को, 2 से लेकर $n - 1$ तक, आज़माना, और जैसे ही कोई विभाजित कर दे, संख्या को संयुक्त घोषित कर देना। यह पाठ लूप का सबसे छोटे भाजक वाला लूप है, और यह सही है। फिर भी, दस अंकों की किसी अभाज्य संख्या के लिए यह लगभग एक हज़ार करोड़ विभाजन करता है, और उनमें से लगभग सभी व्यर्थ हैं, जिसका कारण यह है।

इससे निष्कर्ष निकलता है कि विभाजनों की संख्या लगभग $n$ से घटकर लगभग $\sqrt{n}$ रह जाती है: दो अरब के आसपास के $n$ के लिए, दो अरब से घटकर छियालीस हज़ार। प्रोग्राम पाठ सही लूप की रचना के फ़्लैग वाले पैटर्न का उपयोग करता है: isPrime सत्य से शुरू होता है और यदि लूप को कोई भाजक मिल जाए तो वह उसे हटा देता है।

#include <iostream>#include <print>​int main(){    int n{};    std::cin >> n;    bool isPrime{n >= 2};    for (int d{2}; isPrime && d <= n / d; ++d) {        if (n % d == 0) {            isPrime = false;        }    }    if (isPrime) {        std::println("{} अभाज्य है", n);    } else {        std::println("{} अभाज्य नहीं है", n);    }}

2147483647

2147483647 अभाज्य है

तीन निर्णय टिप्पणी के योग्य हैं। फ़्लैग को n >= 2 से प्रारंभिक मान दिया जाता है, जिससे 0, 1 और ऋणात्मक संख्याएँ लूप में प्रवेश किए बिना अभाज्य नहीं घोषित हो जाती हैं: इस स्थिति को भूल जाना आम त्रुटि है, क्योंकि $n = 1$ होने पर लूप एक भी चक्कर नहीं लगाता और प्रोग्राम 1 को अभाज्य घोषित कर देता। for की शर्त के दो हिस्से हैं: फ़्लैग, जो पहले भाजक पर लूप को रोक देता है, और सीमा। और सीमा d <= n / d लिखी गई है, जो धनात्मक पूर्णांकों के लिए $d^2 \leq n$ के तुल्य है (पूर्णांक विभाजन भिन्नात्मक हिस्सा काट देता है, पर $d$ कटे हुए भागफल से ठीक तभी बड़ा नहीं होता जब वह $n/d$ से बड़ा नहीं होता, क्योंकि $d$ पूर्णांक है)। इनपुट की संख्या, $2^{31} - 1$, सबसे बड़ा int है और अभाज्य है; प्रोग्राम इसका निर्णय $46\,339$ शेषफलों से करता है, अर्थात 2 से $46\,340$ तक के उम्मीदवारों के शेषफलों से।

लूप का निश्चर है: 2 से $d - 1$ तक का कोई भी पूर्णांक $n$ को विभाजित नहीं करता, जब तक फ़्लैग सत्य बना रहे। प्रवेश करते समय यह सत्य है, जब 2 से 1 तक का अंतराल रिक्त होता है; यह बना रहता है, क्योंकि यदि $d$, $n$ को विभाजित नहीं करता तो अंतराल में केवल एक ऐसी संख्या जुड़ती है जो विभाजित नहीं करती; और फ़्लैग के सत्य रहते बाहर निकलने पर, निश्चर और असत्य शर्त, $d^2 > n$, मिलकर कहते हैं कि $\sqrt{n}$ तक का कोई भी उम्मीदवार $n$ को विभाजित नहीं करता, जो ठीक वही है जिसकी साध्य माँग करता है। वैरिएंट उन उम्मीदवारों की संख्या है जिन्हें अभी आज़माना बाक़ी है, अर्थात $d$ और $\sqrt{n}$ के बीच के पूर्णांकों की संख्या: यह हर चक्कर में एक घटती है और शून्य से नीचे नहीं जाती।

ओवरफ़्लो होने वाली शर्त

सीमा लिखने का स्वाभाविक तरीका d * d <= n है, और यह गलत है। उसी इनपुट के साथ लूप $d = 46\,341$ तक पहुँचता है, और तब गुणनफल $46\,341^2 = 2\,147\,488\,281$, int के अधिकतम मान से बड़ा हो जाता है।

#include <iostream>#include <print>​int main(){    int n{};    std::cin >> n;    bool isPrime{n >= 2};    for (int d{2}; isPrime && d * d <= n; ++d) {        if (n % d == 0) {            isPrime = false;        }    }    std::println("अभाज्य? {}", isPrime);}

2147483647

main.cpp:9:33: runtime error: signed integer overflow: 46341 * 46341 cannot be represented in type 'int'

अपरिभाषित व्यवहार का डिटेक्टर प्रोग्राम को गुणनफल पर रोक देता है। उसके बिना, साइन वाले पूर्णांकों का ओवरफ़्लो अपरिभाषित व्यवहार है, और मानक नहीं बताता कि क्या होता है। Linux पर GCC के साथ, ऑप्टिमाइज़ेशन के साथ और उसके बिना भी, जो दिखता है वह शिक्षाप्रद है: गुणनफल घूमकर ऋणात्मक या $n$ से छोटा हो जाता है, और चूँकि कोई भी int अधिकतम मान से बड़ा नहीं होता, शर्त d * d <= n फिर कभी असत्य नहीं होती; लूप लगभग दो अरब चक्करों तक उम्मीदवारों को आज़माता रहता है, जब तक वह $d = n$ तक नहीं पहुँच जाता, जो $n$ को विभाजित करता है, और प्रोग्राम एक अभाज्य संख्या को संयुक्त घोषित कर देता है। ओवरफ़्लो की त्रुटि ओवरफ़्लो के रूप में नहीं, बल्कि गलत उत्तर के रूप में प्रकट होती है। रूप d <= n / d ओवरफ़्लो नहीं हो सकता, क्योंकि वह गुणा करने के बजाय भाग देता है; पाठ बिट और गणितीय लाइब्रेरी ने एक और रास्ता दिया था, std::sqrt से सीमा की एक बार गणना करना, पर तब सीमा की सटीकता फ़्लोटिंग-पॉइंट के पूर्णांकन पर निर्भर करती है, और पूर्णांक विभाजन में यह समस्या नहीं है।

पाठ्यक्रम “बीजगणित और ज्यामिति I” का पाठ “अभाज्य संख्याएँ और अंकगणित की आधारभूत प्रमेय” सिद्ध करता है कि 1 से बड़ा हर पूर्णांक केवल एक ही तरह से अभाज्य संख्याओं का गुणनफल है; परीक्षण-विभाजन यह गुणनफल खोजने का सबसे सीधा तरीका है: मिले हुए हर भाजक से $n$ को भाग देते जाना और भागफल के साथ आगे बढ़ना।