एराटोस्थनीज की छलनी एल्गोरिथ्म: Python, C++ उदाहरण

एराटोस्थनीज की छलनी सबसे सरल अभाज्य संख्या छलनी है। यह एक अभाज्य संख्या एल्गोरिथ्म है जो किसी निश्चित सीमा में सभी अभाज्य संख्याओं को खोजता है। कई अभाज्य संख्या छलनी हैं। उदाहरण के लिए- एराटोस्थनीज की छलनी, एटकिन की छलनी, सुंदरम की छलनी, आदि।

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

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

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

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

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

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

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

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

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

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

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

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

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

एन=ए*बी

पुनः, 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++ कोड उदाहरण

#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 कार्यक्रम का उदाहरण

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() सहायक स्थान.

समय जटिलता:

एराटोस्थनीज एल्गोरिथ्म की नियमित छलनी की समय जटिलता 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 +…….∞) = लॉग(लॉग(एन))

तो, समय जटिलता होगी-

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

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

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

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

सारांश

• एराटोस्थनीज की छलनी एक निश्चित ऊपरी सीमा में अभाज्य संख्याओं को छान देती है।
• अभाज्य संख्या को फ़िल्टर करना सबसे छोटी अभाज्य संख्या, “2” से शुरू होता है। यह क्रमिक रूप से किया जाता है।
• पुनरावृत्ति n के वर्गमूल तक की जाती है, जहाँ n दी गई संख्या सीमा है।
• इन पुनरावृत्तियों के बाद जो संख्याएं बचती हैं वे अभाज्य संख्याएं होती हैं।