एक अभाज्य संख्या (Prime number) वह संख्या है जो केवल दो संख्याओं से विभाज्य होती है: स्वयं और एक। किसी संख्या का गुणनखंड (factor) वह संख्या है जो इसे विभाजित कर सकती है।
पहली दस अभाज्य संख्याओं की सूची है: 2, 3, 5, 7, 11, 13, 17, 23, 29, 31।
जो संख्या अभाज्य नहीं है वह मिश्रित संख्या (composite number) है। एक मिश्रित संख्या वह संख्या है जिसे दो से अधिक संख्याओं से विभाजित किया जा सकता है।
अभाज्य और मिश्रित के अलावा 1 है जो न तो अभाज्य है और न ही मिश्रित क्योंकि इसे केवल स्वयं से विभाजित किया जा सकता है।
कैसे जांचें कि कोई संख्या अभाज्य है या मिश्रित? किसी संख्या के अभाज्य होने के लिए दो शर्तों की जांच करनी चाहिए:
1) यह 1 से बड़ी पूर्ण संख्या होनी चाहिए।
2) इसके केवल दो गुणनखंड होने चाहिए यानी एक और संख्या स्वयं।
यदि ये दो शर्तें पूरी होती हैं, तो हम कह सकते हैं कि संख्या अभाज्य है।
हमारे प्रोग्राम में, हम संख्या को उससे छोटी प्रत्येक संख्या से विभाजित करके जांचेंगे। यदि दी गई संख्या से छोटी कोई संख्या इसे विभाजित करती है तो यह अभाज्य संख्या नहीं है। अन्यथा, यह एक अभाज्य संख्या है।
आइए दो संख्याओं का उदाहरण लें और जांचें कि क्या वे इस प्रक्रिया का उपयोग करके अभाज्य हैं या नहीं।
Input - Number1 - 42 Output - 42 अभाज्य संख्या नहीं है
तर्क - हम 42 को 1 से बड़ी और 42 से छोटी हर संख्या से विभाजित करेंगे। तो,
42/2 = 21 यानी 42, 2 से विभाज्य है, इसका मतलब 42 अभाज्य संख्या नहीं है क्योंकि यह किसी अन्य संख्या से विभाज्य है।
Input - Number2 - 7 Output - 7 एक अभाज्य संख्या है
तर्क - हम 7 को 1 से बड़ी और 7 से छोटी हर संख्या से विभाजित करेंगे। तो,
7, 2 से विभाज्य नहीं है, इसलिए कोड अगली संख्या यानी 3 की जांच करेगा
7, 3 से विभाज्य नहीं है, इसलिए कोड अगली संख्या यानी 4 की जांच करेगा
7, 4 से विभाज्य नहीं है, इसलिए कोड अगली संख्या यानी 5 की जांच करेगा
7, 5 से विभाज्य नहीं है, इसलिए कोड अगली संख्या यानी 6 की जांच करेगा
7, 6 से विभाज्य नहीं है, इसका मतलब है कि 7 केवल 1 और 7 से विभाज्य है इसका मतलब 7 एक अभाज्य संख्या है।
उपरोक्त तर्क को देखें यदि संख्या 1000 प्लस या 100000 प्लस होगी तो प्रोग्राम को फॉर लूप के लिए उतनी ही पुनरावृत्तियों की आवश्यकता होगी यह विधि बहुत अधिक गणना समय लेगी। तो पुनरावृत्तियों की संख्या को कम करने का एक बेहतर तरीका होना चाहिए।
इसका एक अनुकूलित समाधान है लूप को केवल आधे तक चलाना। इसका मतलब है यदि संख्या 77 है तो लूप केवल 38 तक चलेगा। यह आवश्यक पुनरावृत्तियों की संख्या को कम कर देगा इसलिए हम अपने प्रोग्राम को बनाने के लिए इस एल्गोरिदम का उपयोग करेंगे।
उदाहरण
#include <stdio.h>
int main() {
int num = 33, flag = 0;
for(int i=2 ; i < num/2 ; i++) {
if(num%i == 0) {
printf("%d अभाज्य संख्या नहीं है", num);
flag = 1;
break;
}
}
if(flag == 0) {
printf("%d एक अभाज्य संख्या है", num);
}
}
आउटपुट
33 एक अभाज्य संख्या है
