የኢራቶስቴንስ ሲኢቭ


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን ፓም አቢይ አንድ GE የጤና google MAQ የ Microsoft Qualcomm VMware
ተለዋዋጭ ፕሮግራም ሒሳብ

የኢራቶስቴንስ ሲኢቭ ከኤን በታች የሆኑትን ዋና ቁጥሮች የምናገኝበት ስልተ-ቀመር ነው እዚህ ኤን አንድ ነው ኢንቲጀር እሴት ዋናዎቹን ቁጥሮች ወደ ገደብ ለማወቅ ይህ ቀልጣፋ ዘዴ ነው ፡፡ ይህንን በመጠቀም እስከ 10000000 ድረስ ዋናዎቹን ቁጥሮች ማወቅ እንችላለን ፡፡ እዚህ መሠረታዊው አካሄድ ጥቅም ላይ የዋለ እኛ የመጠን ትዝታ (N-1) ብቻ እናደርጋለን ፡፡ እሴቱን በተከታታይ ከ 2 እስከ N በማስታወሻ ውስጥ ያከማቹ። አሁን በማስታወሻው ውስጥ ከሚገኘው ከመጀመሪያው የማይለየውን ቁጥር እንሻገራለን ይህም 2 ነው ፡፡ ከዚያ ሁሉንም የ 2 ቁጥር እስከ N. ምልክት እናደርጋለን ፡፡ አሁን በማስታወሻው ውስጥ ወደሚቀጥለው ምልክት ያልተደረገ ቁጥር እንሸጋገራለን ፡፡ 3 ምልክት ያልተደረገባቸው ፡፡ እስኩዌር (N) እስክንደርስ ድረስ ይህንን ሂደት ይድገሙት። እዚህ የእኛ ዋና ቁጥር ያልተሰየመ ቁጥር ፡፡ ስለዚህ ፣ አንድ ተጨማሪ ጊዜ ብቻ እንመድባለን እና በመልሱ ውስጥ እናከማቸዋለን ፡፡ የኢራቶስቴንስ ሲቭ እንዴት እንደሚሠራ እንመልከት ፡፡

ምሳሌ በመጠቀም መሥራት

ደረጃ 1

ከ 2 እስከ N ያሉትን ቁጥሮች የያዘ የማስታወሻ ቁልፍ ይፍጠሩ (እዚህ 100 እንወስዳለን)።

የኢራቶስቴንስ ሲኢቭ

ደረጃ 2

በማስታወሻው ውስጥ የመጀመሪያውን ያልታወቀ ቁጥር ሁሉንም ብዜቶች ምልክት ያድርጉበት 2 ይህም።

የኢራቶስቴንስ ሲኢቭ

ደረጃ 3

አሁን በሚቀጥለው ምልክት ያልተደረገበት ቁጥር ሁሉንም ብዜቶች በማስታወሻ ውስጥ 3 ነው ፡፡

የኢራቶስቴንስ ሲኢቭ

ደረጃ 4

ወደ ቀጣዩ የማያስታውቅ ቁጥር ውሰድ ይህም 5. ነው 5. አሁን ሁሉንም የ XNUMX ብዜቶችን ምልክት ያድርጉባቸው ፡፡

ደረጃ 5

በክልል 2 ውስጥ የመጨረሻው ያልተለየነው ቁጥራችን ወደሚቀጥለው ወደማይታወቅ ቁጥር ይሂዱ ወደ N ስኩዌር ሥሩ ፡፡

ደረጃ 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 

የጊዜ ውስብስብነት

ኦ (N * ምዝግብ ማስታወሻ (logN)) ዋና ቁጥሮቹን እስክናገኝ ድረስ N ገደቡ የት ነው። እዚህ loglogN የሚመጣው በሚከተለው ንድፍ ውስጥ ባለው የ loop ሩጫ ምክንያት ነው።

ለ 2 -> N / 2 ጊዜ ይሠራል ፣ ለ 3 -> N / 3 ጊዜ ይሠራል ፣ ለ 5 -> N / 5 ጊዜ ይሠራል…

ስለዚህ ፣ N * (1/2 + 1/3 + 1/5 + 1/7 + ……) = N * log (logN)

ማስታወሻ-ሃርሞኒክ ግስጋሴ የዋናዎቹ ድምር N የውሎች ብዛት ካለው ምዝግብ ማስታወሻ (logN) ጋር እኩል ነው።

የቦታ ውስብስብነት

ኦ (ኤን) ዋና ቁጥሮቹን እስክናገኝ ድረስ N ገደቡ የት ነው። ምልክት ለማድረግ የምንጠቀምባቸውን ቁጥሮች ለማከማቸት ይህንን ቦታ እንጠቀማለን ፡፡

ማጣቀሻዎች