Eratosthenlərin ələk

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon alma Capital One GE Healthcare google MAQ microsoft Qualcomm VMware
Dinamik proqramlaşdırma RiyaziyyatBaxılıb 35

Eratosthenlərin ələk N-dən az olan əsas rəqəmləri tapdığımız bir alqoritmdir. Burada N bir tam dəyər. Bu, əsas rəqəmləri bir həddə tapmaq üçün səmərəli bir üsuldur. Bunu istifadə edərək 10000000-a qədər olan əsas rəqəmləri öyrənə bilərik. Burada əsas yanaşmadan istifadə olunur, sadəcə N-1 ölçüsündə yaddaş saxlayırıq. Dəyəri yaddaşda 2-dən N-ə qədər davamlı olaraq saxlayın. İndi yaddaşdakı ilk işarəsiz nömrədən 2-yə keçirik. Sonra 2-nin N-ə qədər olan bütün vurmalarını qeyd edirik. İndi yaddaşdakı növbəti işarəsiz nömrəyə keçirik. İndi isə 3 işarəsizdir. Sqrt (N) səviyyəsinə çatana qədər bu əməliyyatı təkrarlayın. İndi əsas nömrəmizin qeyd olunmayan nömrəsi. Beləliklə, yalnız bir dəfə təkrarlayırıq və cavabda saxlayırıq. Eratosthenes Sieve'in necə işlədiyini görək.

Nümunədən istifadə edərək işləyirik

Addım 1

2-dən N-ə qədər rəqəmlər olan bir yaddaş yaradın (Burada 100 alırıq).

Eratosthenlərin ələkPin

Addım 2

Yaddaşdakı ilk işarəsiz rəqəmin bütün vurmalarını 2 olan işarələyin.

Eratosthenlərin ələkPin

Addım 3

İndi yaddaşdakı 3 olan işarələnməmiş nömrənin hamısını vurun.

Eratosthenlərin ələkPin

Addım 4

5-dən sonrakı işarəsiz nömrəyə keçin. İndi 5-in bütün vurmalarını qeyd edin.

Pin

Addım 5

2 aralığında son işarələnməmiş sayımız olan növbəti işarəsiz nömrəyə keçərək N kvadrat kökünə keçin.

Pin

Addım 6

Qalan qeyd olunmamış nömrələrin hamısı əsas nömrələrimizdir.

Baş Nömrələr: 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.

Alqoritm

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.

Həyata keçirilməsi

/*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 

Zamanın mürəkkəbliyi

O (N * log (logN)) burada N sayları tapmaq lazım olana qədər limitdir. Budur loglogN aşağıdakı nümunədə işlədilən döngə səbəbi ilə gəlir.

2 -> N / 2 dəfə, 3 -> N / 3 dəfə, 5 -> N / 5 dəfə çalışır ...

Beləliklə, N * (1/2 + 1/3 + 1/5 + 1/7 + ……) = N * log (logN).

Qeyd: Harmonik Tərəqqi ilklərin cəminin log (logN) -ə bərabərdir, burada N şərtlərin sayıdır.

Kosmik Mürəkkəblik

O (N) burada N sayları tapmaq lazım olana qədər limitdir. Bu boşluğu işarələmək üçün istifadə etdiyimiz nömrələri saxlamaq üçün istifadə edirik.

References

Translate »