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.
Mündəricat
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).
Addım 2
Yaddaşdakı ilk işarəsiz rəqəmin bütün vurmalarını 2 olan işarələyin.
Addım 3
İndi yaddaşdakı 3 olan işarələnməmiş nömrənin hamısını vurun.
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.
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.
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.
