एराटोस्थेनिस चाळणी


अडचण पातळी मध्यम
वारंवार विचारले ऍमेझॉन सफरचंद कॅपिटल वन जीई हेल्थकेअर Google एमक्यू मायक्रोसॉफ्ट Qualcomm व्हीएमवेअर
डायनॅमिक प्रोग्रामिंग गणित

एराटोस्थेनिस चाळणी एक अल्गोरिदम आहे ज्यामध्ये आम्हाला एनपेक्षा कमी संख्या आढळतात. येथे एन आहे पूर्णांक मूल्य. मर्यादेपर्यंत मुख्य संख्या शोधण्यासाठी ही एक प्रभावी पद्धत आहे. याचा उपयोग करून आपण 10000000 पर्यंत मूळ संख्या शोधू शकतो. येथे मूळ दृष्टीकोन वापरला जातो आम्ही फक्त एन -1 आकाराची मेमरी बनवितो. मेमरीमध्ये 2 ते N पर्यंत सतत मूल्य ठेवा. आता आपण मेमरी मधील पहिल्या चिन्हांकित क्रमाकांकडे पाठ करतो जे 2 आहे. नंतर आम्ही 2 पर्यंतची सर्व गुणाकार एन पर्यंत चिन्हांकित करतो. आता आपण मेमरीच्या पुढील अंकात संख्या 3 वर जाऊ. आता आम्ही सर्व गुणाकार चिन्हांकित करतो. 3 जे चिन्हांकित नाहीत. आम्ही स्क्वेअर (एन) पर्यंत पोहोचत नाही तोपर्यंत ही प्रक्रिया पुन्हा करा. येथे आता आमच्या प्राथमिक क्रमांकाची अचिन्हांकित संख्या. तर, आम्ही पुन्हा एकदा पुनरावृत्ती करतो आणि त्या उत्तरात संचयित करतो. चला सिव्हि ऑफ एराटोस्थनेस कसे कार्य करते ते पाहू.

उदाहरण वापरुन काम करणे

पायरी 1

2 ते एन पर्यंतची संख्या असलेली मेमरी विच तयार करा (येथे आम्ही 100 घेतो).

एराटोस्थेनिस चाळणी

पायरी 2

मेमरीमध्ये प्रथम अचिन्ह संख्येची सर्व गुणाकार चिन्हांकित करा जी 2 आहे.

एराटोस्थेनिस चाळणी

पायरी 3

आता सर्व गुणाकार चिन्हांकित करा पुढील अचिन्हांकित संख्या जे मेमरीमध्ये 3 आहे.

एराटोस्थेनिस चाळणी

पायरी 4

5 पुढील पुढील चिन्हांकित नंबरवर जा. 5 च्या सर्व गुणकांना चिन्हांकित करा.

पायरी 5

पुढील अचिन्हांकित संख्येकडे जा जो आमच्या श्रेणी 2 मधील अखेरची अचिन्हांकित संख्या एन च्या वर्गमूलकडे जा.

पायरी 6

उर्वरित सर्व चिन्हांकित न केलेले क्रमांक आमची मुख्य संख्या आहेत.

मुख्य क्रमांक: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 41, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 , 97.

अल्गोरिदम

Step:1 Store the number from 2 to N in the list.
Step:2 Set all numbers as unmarked.
Step:3 For i in range 2 to Sqrt(N):
       If i is unmarked then:
          Marked all the multiples of i.
Step:4 Print all the unmarked numbers.

अंमलबजावणी

/*C++ Implementation for Sieve of Eratosthenes.*/ 
#include<bits/stdc++.h>
using namespace std;
bool marked[1000000];
void Sieve(int n)
{
    /*for i from 2 to sqrt(N)*/
    for(int i=2;i*i<=n;i++) 
    {
        /*if i is unmarked*/
        if(marked[i]==false) 
        {  
            /*marked all the multiples of i*/
            for(int j=i*i;j<=n;j+=i) 
            {
                /*marked*/
                marked[j] = true; 
            }
        } 
    }
    cout<<"Prime number from 2 to N are: "<<endl;
    for(int i=2;i<=n;i++) 
    {
       if(marked[i]==false) 
       {
          cout<<i<<" "; 
       }
    }
    cout<<endl;
}
int main() 
{ 
    /*Take input N*/
    int n;
    cin>>n;
    /*call the sieve function*/
    Sieve(n);
    return 0; 
}
100
Prime number from 2 to N are: 
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 

वेळ कॉम्प्लेक्सिटी

ओ (एन * लॉग (लॉगएन)) जिथे एन ही मर्यादा आहे जिथेपर्यंत आपल्याला प्राथमिक संख्या शोधण्याची गरज नाही. येथे लॉगऑन खालील नमुना मध्ये पळवाट धावल्यामुळे येते.

2 -> ते एन / 2 वेळा चालते, 3 -> ते एन / 3 वेळा, 5 साठी -> ते एन / 5 वेळा चालवते…

तर, एन * (1/2 + 1/3 + 1/5 + 1/7 + ……) = एन * लॉग (लॉगएन).

टीपः हार्मोनिक प्रगती प्राइमची बेरीज लॉग (लॉगएन) च्या बरोबरी असते जिथे एन अटींची संख्या असते.

स्पेस कॉम्प्लेक्सिटी

ओ (एन) जिथे एन ही मर्यादा आहे जिथेपर्यंत आपल्याला प्राथमिक संख्या शोधण्याची नाहीत. आम्ही हे स्थान आम्ही चिन्हांकित करण्यासाठी वापरत असलेल्या संख्या संग्रहित करण्यासाठी वापरतो.

संदर्भ