एराटोस्थनीज की छलनी Python & C++

एराटोस्थनीज की छलनी क्या है?

एराटोस्थनीज की छलनी सबसे सरल अभाज्य संख्या छलनी विधि है। यह एक अभाज्य संख्या एल्गोरिदम है जिसका उपयोग दी गई सीमा के भीतर सभी अभाज्य संख्याओं को खोजने के लिए किया जाता है। एराटोस्थनीज की छलनी, एटकिन की छलनी और सुंदरम की छलनी सहित कई अभाज्य संख्या छलनी विधियाँ मौजूद हैं।

शब्द "चलनी"छलनी" से तात्पर्य पदार्थों को छानने वाले उपकरण से है। इसी भावना से प्रेरित होकर, छलनी एल्गोरिदम का प्रयोग किया गया है। Python और अन्य भाषाओं में इसका तात्पर्य पूर्णांकों की सूची से अभाज्य संख्याओं को अलग करने की विधि से है।

यह एल्गोरिदम पुनरावृत्ति विधि का उपयोग करके अभाज्य संख्याओं को फ़िल्टर करता है। फ़िल्टरिंग प्रक्रिया सबसे छोटी अभाज्य संख्या से शुरू होती है। अभाज्य संख्या 1 से बड़ी एक प्राकृतिक संख्या होती है जिसके केवल दो भाजक होते हैं, अर्थात् 1 और वह संख्या स्वयं। Numbers जो संख्याएँ अभाज्य संख्याएँ नहीं होतीं, उन्हें भाज्य संख्याएँ कहते हैं।

एराटोस्थनीज की छलनी का उपयोग क्यों किया जाता था?

एराटोस्थनीज की छलनी विधि में, सबसे पहले एक छोटी अभाज्य संख्या का चयन किया जाता है, और उसके सभी गुणजों को छानकर अलग कर दिया जाता है। यह प्रक्रिया एक निश्चित सीमा में लूप में चलती है, जिससे प्रत्येक उम्मीदवार पर परीक्षण विभाजन किए बिना कुशलतापूर्वक n तक की सभी अभाज्य संख्याएँ प्राप्त हो जाती हैं।

इससे छलनी विधि एक-एक करके अभाज्य संख्याओं की जाँच करने की तुलना में तेज़ हो जाती है। इसका व्यापक रूप से संख्या सिद्धांत, क्रिप्टोग्राफी, हैशिंग और प्रतिस्पर्धी प्रोग्रामिंग में उपयोग किया जाता है जहाँ कई अभाज्य संख्याओं को शीघ्रता से उत्पन्न करना आवश्यक होता है।

उदाहरण के लिए:

आइए 2 से 10 तक की संख्या सीमा लें।

एराटोस्थनीज की छलनी विधि लागू करने के बाद, यह अभाज्य संख्याओं 2, 3, 5, 7 की सूची तैयार करेगा।

एराटोस्थनीज की एल्गोरिथ्म छलनी

एराटोस्थनीज़ की छलनी के लिए एल्गोरिथ्म इस प्रकार है:

चरण 1) 2 से लेकर दी गई सीमा n तक की संख्याओं की एक सूची बनाएं। हम 2 से शुरू करते हैं क्योंकि यह सबसे छोटी और पहली अभाज्य संख्या है।

चरण 2) सूची में सबसे छोटी संख्या x का चयन करें (प्रारंभ में x का मान 2 है), सूची में आगे बढ़ें और चयनित संख्या के सभी गुणजों को चिह्नित करके संबंधित भाज्य संख्याओं को फ़िल्टर करें।

चरण 3) फिर सूची में अगला अभाज्य या सबसे छोटी अचिह्नित संख्या चुनें और चरण 2 को दोहराएं।

चरण 4) पिछले चरण को तब तक दोहराएं जब तक कि x का मान n के वर्गमूल से कम या उसके बराबर न हो जाए (x<=).

नोट: गणितीय तर्क काफी सरल है। संख्या श्रेणी n को इस प्रकार गुणनखंडित किया जा सकता है:

n = a * b

पुनः, n = *

= (इससे छोटा कारक ) * (इससे बड़ा कारक )

तो कम से कम एक प्रधान कारण या दोनों <= होना चाहिए इसलिए, ऊपर की ओर यात्रा करते हुए काफी होगा।

चरण 5) उन चार चरणों के बाद, शेष अचिह्नित संख्याएँ उस दी गई श्रेणी n में सभी अभाज्य संख्याएँ होंगी।

हल किया गया उदाहरण

उदाहरण:

आइए एक उदाहरण लेकर देखें कि यह कैसे काम करता है।

इस उदाहरण के लिए, हम 2 से 25 तक की अभाज्य संख्याओं की सूची ज्ञात करेंगे। अतः, n = 25।

चरण 1) पहले चरण में, हम 2 से 25 तक की संख्याओं की एक सूची लेंगे क्योंकि हमने n = 25 का चयन किया है।

चरण 2) फिर हम सूची में से सबसे छोटी संख्या, x का चयन करते हैं। प्रारंभ में x = 2 होता है क्योंकि यह सबसे छोटी अभाज्य संख्या है। फिर हम सूची में आगे बढ़ते हैं और 2 के गुणजों को चिह्नित करते हैं।

n के दिए गए मान के लिए 2 के गुणज हैं: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.

नोट: नीला रंग चयनित संख्या को दर्शाता है, और गुलाबी रंग हटाए गए गुणजों को दर्शाता है।

चरण 3) फिर हम अगली सबसे छोटी अचिह्नित संख्या चुनते हैं, जो 3 है, और 3 के गुणजों को चिह्नित करके अंतिम चरण को दोहराते हैं।

चरण 4) हम चरण 3 को उसी तरह दोहराते हैं जब तक कि x = या 5

चरण 5) शेष अचिह्नित संख्याएँ 2 से 25 तक की अभाज्य संख्याएँ हैं।

झूठाCode

निम्नलिखित स्यूडो-कोड, एराटोस्थनीज की छलनी की मूल संरचना को दर्शाता है, इससे पहले कि हम इसे वास्तविक कोड में अनुवादित करें।

Begin
	Declare a boolean array of size n and initialize it to true
	For all numbers i : from 2 to sqrt(n)
     		IF bool value of i is true THEN
         			i is prime
         			For all multiples of i (i<n)
             			mark multiples of i as composite
Print all unmarked numbers
End

एराटोस्थनीज सी की छलनीC++ Code उदाहरण

नीचे एक पूर्ण विवरण दिया गया है। C++ एराटोस्थनीज की छलनी का वह कार्यान्वयन जो चुनी हुई ऊपरी सीमा तक प्रत्येक अभाज्य संख्या को प्रिंट करता है।

#include <iostream>
#include <cstring>
using namespace std;
void Sieve_Of_Eratosthenes(int n)
{
    // Create and initialize a boolean array
    bool primeNumber[n + 1];
    memset(primeNumber, true, sizeof(primeNumber));
    for (int j = 2; j * j <= n; j++) {
        if (primeNumber[j] == true) {
            // Update all multiples of i as false
            for (int k = j * j; k <= n; k += j)
                primeNumber[k] = false;
        }
    }
    for (int i = 2; i <= n; i++)
        if (primeNumber[i])
            cout << i << " ";
}
int main()
{
    int n = 25;
    Sieve_Of_Eratosthenes(n);
    return 0;
}

आउटपुट:

2 3 5 7 11 13 17 19 23

एराटोस्थनीज की छलनी Python कार्यक्रम का उदाहरण

निम्नलिखित Python यह प्रोग्राम एक बूलियन सूची और एक while लूप का उपयोग करके उसी एल्गोरिदम को लागू करता है।

def SieveOfEratosthenes(n):
# Create a boolean array
	primeNumber = [True for i in range(n+2)]
	i = 2
	while (i * i <= n):
		if (primeNumber[i] == True):
			# Update all multiples of i as false
			for j in range(i * i, n+1, i):
				primeNumber[j] = False
		i += 1
	for i in range(2, n):
		if primeNumber[i]:
			print(i)
n = 25
SieveOfEratosthenes(n)

आउटपुट:

2
3
5
7
11
13
17
19
23

खंडित छलनी

हमने देखा है कि एराटोस्थनीज की छलनी संख्याओं की पूरी श्रृंखला में एक लूप चलाती है। इसलिए, संख्याओं को संग्रहित करने के लिए इसे O(n) मेमोरी स्पेस की आवश्यकता होती है। स्थिति तब जटिल हो जाती है जब हम एक विशाल श्रृंखला में अभाज्य संख्याएँ खोजने का प्रयास करते हैं, क्योंकि बड़े n के लिए इतनी बड़ी मेमोरी ब्लॉक आवंटित करना संभव नहीं होता है।

कुछ नई विशेषताओं को शामिल करके एल्गोरिथ्म को अनुकूलित किया जा सकता है। विचार यह है कि संख्या श्रेणी को छोटे खंडों में विभाजित किया जाए और उन खंडों में एक-एक करके अभाज्य संख्याओं की गणना की जाए। यह स्पेस जटिलता को कम करने का एक कुशल तरीका है। इस विधि को कहा जाता है खंडित छलनी.

अनुकूलन निम्नलिखित तरीके से प्राप्त किया जा सकता है:

1. 2 से लेकर अभाज्य संख्याएँ खोजने के लिए एक सरल छलनी का उपयोग करें और उन्हें एक सरणी में संग्रहीत करें.
2. श्रेणी [0…n-1] को अधिकतम आकार के कई खंडों में विभाजित करें .
3. प्रत्येक खंड के लिए, खंड के माध्यम से पुनरावृति करें और चरण 1 में पाए गए अभाज्य संख्याओं के गुणजों को चिह्नित करें। इस चरण में O(अधिकतम पर।

नियमित छलनी को O(n) सहायक मेमोरी स्थान की आवश्यकता होती है, जबकि खंडित छलनी को O(), जो कि बड़े n के लिए एक महत्वपूर्ण सुधार है। इस विधि की एक कमी भी है, क्योंकि यह समय जटिलता में सुधार नहीं करती है।

जटिलता विश्लेषण

स्थानिक और समय जटिलता दोनों को समझने से आपको किसी दिए गए समस्या आकार के लिए नियमित छलनी और खंडित छलनी के बीच चयन करने में मदद मिलती है।

अंतरिक्ष जटिलता:

एराटोस्थनीज की सरल छलनी एल्गोरिदम को O(n) मेमोरी स्पेस की आवश्यकता होती है। खंडित छलनी को O(n) मेमोरी स्पेस की आवश्यकता होती है।) सहायक स्थान.

समय जटिलता:

एराटोस्थनीज की छलनी विधि के नियमित एल्गोरिदम की समय जटिलता O(n*log(log(n))) है। इस जटिलता के पीछे के तर्क पर नीचे चर्चा की गई है।

किसी दी गई संख्या n के लिए, भाज्य संख्या (अर्थात अभाज्य संख्या नहीं) को चिह्नित करने में लगने वाला समय स्थिर होता है। अतः, लूप के चलने की संख्या निम्न के बराबर होती है:

n/2 + n/3 + n/5 + n/7 + ……∞

= एन * (1/2 + 1/3 + 1/5 + 1/7 +…….∞)

अभाज्य संख्याओं के योग की हार्मोनिक प्रगति को log(log(n)) के रूप में निकाला जा सकता है:

(1/2 + 1/3 + 1/5 + 1/7 +…….∞) = लॉग(लॉग(एन))

अतः, समय जटिलता इस प्रकार होगी:

T(n) = n * (1/2 + 1/3 + 1/5 + 1/7 + ……∞)

= एन * लॉग(लॉग(एन))

इस प्रकार समय जटिलता O(n * log(log(n))) है।

आगे आप इसके बारे में जानेंगे। पास्कल का त्रिभुज.

अक्सर पूछे जाने वाले प्रश्न