Эратосфены шигшүүр


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Амазоны Apple-ийн Капитал Нэг GE Эрүүл мэндийн Google-ийн MAQ Microsoft- Qualcomm VMware
Динамик програмчлал Математик

Эратосфены шигшүүр нь N-ээс бага анхны тоог олдог алгоритм юм. Энд N байна бүхэл тоо үнэ цэнэ. Энэ бол анхны хязгаарыг хязгаарлах хамгийн оновчтой арга юм. Үүнийг ашигласнаар бид 10000000 хүртэлх анхны тоонуудыг олж мэдэх боломжтой. Энд үндсэн аргыг ашигладаг бөгөөд бид зөвхөн N-1 хэмжээтэй санах ойг үүсгэдэг. Санах ойд 2-оос N хүртэл тасралтгүй хадгална. Одоо бид 2-р санах ойд тэмдэглэгдээгүй эхний дугаараас шилжиж, дараа нь 2-ын бүх үржвэрийг N хүртэл тэмдэглэе. Одоо бид дараагийн санах ой дахь 3-р тэмдэггүй дугаар руу шилжинэ. 3 нь тэмдэглэгдээгүй байна. Бид sqrt (N) хүрэх хүртэл энэ үйлдлийг давт. Одоо манай анхны дугаарын тэмдэглэгдээгүй дугаар энд байна. Тиймээс бид дахин нэг удаа давтаж, хариултанд нь хадгална. Sieve of Eratosthenes хэрхэн ажилладагийг харцгаая.

Жишээ ашиглах

1-р алхам

2-оос N хүртэлх тоонуудыг багтаасан санах ойг үүсгэ (энд бид 100-г авна).

Эратосфены шигшүүр

2-р алхам

Санах ойд эхний тэмдэглэгээгүй тооны бүх үржвэрийг тэмдэглэнэ үү.

Эратосфены шигшүүр

3-р алхам

Одоо санах ойд 3 гэсэн тэмдэглэгдээгүй дараагийн бүх үржүүлгийг тэмдэглэ.

Эратосфены шигшүүр

4-р алхам

Дараагийн тэмдэглэгээгүй дугаар болох 5 руу шилжүүлээрэй. Одоо 5-ын бүх үржвэрийг тэмдэглэ.

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 

Цаг хугацааны нарийн төвөгтэй байдал

O (N * log (logN)) энд N нь анхны тоог олох хүртэл хязгаар юм. Энд loglogN дараахь хэв маягаар ажилладаг давталтын улмаас ирдэг.

2 -> N / 2 удаа, 3 -> N / 3 удаа, 5 -> N / 5 удаа ажилладаг ...

Тэгэхээр N * (1/2 + 1/3 + 1/5 + 1/7 + ……) = N * log (logN).

Тэмдэглэл: Гармоник прогресс энгийн тоонуудын нийлбэр нь log (logN) -тэй тэнцүү бөгөөд N нь нэр томъёоны тоо юм.

Сансрын нарийн төвөгтэй байдал

O (N) энд N нь анхны тоог олох хүртэл хязгаар юм. Бид энэ зайг тэмдэглэхдээ ашигладаг тоонуудаа хадгалахад ашигладаг.

Ашигласан материал