Sito eratosteny z C ++

Liczba pierwsza jest naturalną (całą) liczbą, która jest większa lub równa dwóch, którą można podzielić tylko przez siebie i 1. Pierwsze liczby pierwszorzędne to: 2, 3, 5, 7 itd.

W przypadku liczby 5 liczba liczb pierwszych, które są i/lub w tym 5 to:

2, 3, 5

W przypadku liczby 8 liczba liczb pierwszych, które są i/lub w tym 8 to:

2, 3, 5, 7

W przypadku liczby 19 liczba liczb pierwszych, które są i/lub w tym 19 to:

2, 3, 5, 7, 11, 13, 17, 19

W przypadku liczby 25 liczba liczb pierwszych, które są i/lub w tym 25 to:

2, 3, 5, 7, 11, 13, 17, 19, 23

W przypadku liczby 36 liczba liczb pierwszych, które są i/lub w tym 36 to:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31

W przypadku liczby 37 liczba liczb pierwszych, które są i/lub w tym 37 to:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37

Te listy są tylko przykładami. Istnieje wiele innych przykładowych list liczb pierwszych poniżej i/lub w tym danej liczby. Rozpocznij zrozumienie sita Eratosthenes, zauważając, że liczby pierwszorzędne poniżej mniejszej liczby są takie same jak pierwsza część liczb pierwszych poniżej danej większej liczby.

Sito eratosthenes jest techniką znalezienia wszystkich liczb pierwszych, które są mniejsze lub równe danej liczbie, takiej jak 36 lub 37 powyżej. Ta liczba, taka jak 36 lub 37, jest zwykle podawana nazwa zmiennej „N” w programowaniu. Sito eratosteny jest uważane za skuteczny algorytm w celu uzyskania listy liczb pierwszych.

Demonstracja Sieve of Eratostenes

Pytanie brzmi: znajdź liczby pierwszorzędne mniejsze lub równe 5, na przykład w wydajny sposób. Wydajny sposób tutaj oznacza wykorzystanie jak najmniejszej operacji. Liczby pierwszorzędne zaczynają się od 2. Wszystkie liczby, w tym wielokrotności małych liczb pierwszych od 2 do 5 to:

2, 3, 4, 5

W tym zakresie liczba, która nie jest liczbą pierwszą, jest wielokrotnością poprzedniego numeru pierwszego. Wielokrotność można uzyskać poprzez dodanie tej samej liczby pierwszej, w kółko. Na przykład 2 + 2 to 4, plus 2 znowu to 6. I to wykracza poza zasięg. Cztery, które jest wielokrotnością 2, nie powinno znajdować się na liście, ponieważ nie jest to liczba pierwsza. Równanie 3 + 3 wynosi 6, które jest już poza zasięgiem. I 6 lub dowolna liczba poza zasięgiem nie powinna znajdować się na liście. Tak więc wynik jest następujący:

2, 3, 5

Numer, o którym mowa, to 5. Korzeń kwadratowy 5 to 2.24. Wartość liczb całkowita dla pierwiastka kwadratowego 5 wynosi 2. Mnożniki liczb pierwszych poniżej i do 2, czyli wartości całkowitej dla pierwiastka kwadratowego 5, są usuwane z listy wszystkich liczb.

Rozważ teraz numer 8. Wszystkie liczby, w tym wielokrotności małych liczb pierwszych od 2 do 8 to:

2, 3, 4, 5, 6, 7, 8

Równanie 2 + 2 wynosi 4. Cztery wychodzi. Równanie 4+2 wynosi 6. Sześć wychodzi. Równanie 6 + 2 wynosi 8. Osiem jest poza domem. Następny numer pierwotny, który należy wziąć pod uwagę, to 3. Równanie 3 + 3 wynosi 6. Sześć jest już wykluczone przez ciągłe dodawanie 2. Równanie 6 + 3 wynosi 9; To jest poza zasięgiem. Liczby pierwszorzędne między 2 a 8, włączającymi, to:

2, 3, 5, 7

Numer, o którym mowa, to 8. Korzeń kwadratowy 8 to 2.83. Wartość liczb całkowita dla pierwiastka kwadratowego 8 to 2. Mnożniki liczb pierwszych poniżej i do 2, czyli wartości całkowitej dla pierwiastka kwadratowego 8, są usuwane, aby uzyskać wymaganą listę liczb pierwszych.

Podobnym problemem jest wymienienie liczb pierwszych od 2 do 19, włącznie. Wszystkie liczby od 2 do 19, włącznie to:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19

Równanie 2 + 2 wynosi 4; 4 jest poza domem. Równanie 4 + 2 wynosi 6; 6 jest poza domem. Równanie 6 + 2 wynosi 8; 8 jest poza domem. Równanie 8 + 2 wynosi 10; 10 jest poza domem. Równanie 10 + 2 wynosi 12; 12 jest poza domem. Równanie 12 + 2 wynosi 14; 14 jest poza domem. Równanie 14 + 2 wynosi 16; 16 jest poza domem. Równanie 16 + 2 wynosi 18; 18 jest poza domem. Równanie 18 + 2 wynosi 20, czyli powyżej zakresu; 20 jest poza domem.

Kolejna pierwsza liczba do rozważenia, idąc w górę w kierunku korzenia kwadratowego 19, to 3. Równanie 3 + 3 wynosi 6; 6 jest już wykluczony jako wielokrotność 2. Równanie 6 + 3 wynosi 9; 9 wychodzi. Równanie 9 + 3 wynosi 12; 12 jest już wykluczone jako wielokrotność 2. Równanie 12 + 3 wynosi 15; 15 jest poza domem. Równanie 15 + 3 wynosi 18; 18 jest już wykluczony jako wielokrotność 2. Równanie 18 + 3 wynosi 21, czyli powyżej zakresu. Wynik to:

2, 3, 5, 7, 11, 13, 17, 19

Numer, o którym mowa, to 19. Pierwiastek kwadratowy wynosi 4.36. Wartość liczb całkowita dla korzenia kwadratowego 19 to 4. Mnożniki liczb pierwszych poniżej i do 4, które są wartością liczb całą kwadratową 19, są usuwane.

Liczby pierwszorzędne poniżej i do 4 to: 2 i 3. Z powodu 3 nie było sensu usuwać liczby 6, 12 i 18, które mają wielokrotności 3, które są już usunięte jako wielokrotności 2. Tylko wielokrotności 3, które nie są wielokrotnościami 2, są usuwane z powodu 3. W praktyce, po usunięciu wielokrotności 2, tylko wielokrotności z i powyżej 3 x 3 = 9 należy usunąć bez powtarzania usuwania 6. Z powodu 3, liczby do usunięcia wynoszą 9, 12, 15 i 18; z 12 i 18 latami teoretycznie usunięto. Numer 6 należy usunąć raz, a nie dwa razy.

Niech n będzie 25, nowa liczba, o której mowa. Wszystkie liczby od 2 do 25 to:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25

Równanie 2 + 2 wynosi 4; 4 wychodzi. Równanie 4 + 2 wynosi 6; 6 jest poza domem. Równanie 6 + 2 wynosi 8; 8 jest poza domem. Równanie 8 + 2 wynosi 10; 10 jest poza domem. Równanie 10 + 2 wynosi 12; 12 jest poza domem. Równanie 12 + 2 wynosi 14; 14 jest poza domem. Równanie 14 + 2 wynosi 16; 16 jest poza domem. Równanie 16 + 2 wynosi 18; 18 jest poza domem. Równanie 18 + 2 wynosi 20; 20 jest poza domem. Równanie 20 + 2 wynosi 22; 22 jest poza domem. Równanie 22 + 2 wynosi 24; 24 jest poza domem. Równanie 24 + 2 wynosi 26, czyli powyżej zakresu.

Kolejna liczba pierwsza do rozważenia, idąc w górę w kierunku pierwiastka kwadratowego po 25, to 3. Równanie 3 + 3 wynosi 6; 6 jest już wykluczony jako wielokrotność 2. Równanie 6 + 3 wynosi 9; 9 wychodzi. Równanie 9 + 3 wynosi 12. Dwanaście jest już wykluczone jako wielokrotność 2. Równanie 12 + 3 wynosi 15; 15 jest poza domem. Równanie 15 + 3 wynosi 18; 18 jest już wykluczony jako wielokrotność 2. Równanie 18 + 3 wynosi 21; 21 wychodzi. Równanie 21 + 3 wynosi 24; 24 jest już wykluczone jako wielokrotność 2. Równanie 24 + 3 wynosi 27, czyli powyżej zakresu.

Kolejna liczba pierwsza do rozważenia, idąc w górę w kierunku pierwiastka kwadratowego 25, która wynosi 5, wynosi 5. Równanie 5 + 5 wynosi 10; 10 jest już wykluczone jako wielokrotność 2. Równanie 10 + 5 wynosi 15; 15 jest już wykluczone jako wielokrotność 3. Równanie 15 + 5 wynosi 20; 20 jest już wykluczone jako wielokrotność 2. Równanie 20 + 5 wynosi 25; 25 wychodzi. Wynik to:

2, 3, 5, 7, 11, 13, 17, 19, 23

Numer, o którym mowa, to 25. Korzeń kwadratowy 25 to 5. Wartość liczb całkowita dla pierwiastka kwadratowego 25 to 5. Mnożniki liczb pierwszych poniżej i do 5, czyli wartości całkowitej dla pierwiastka kwadratowego 25, są usuwane.

Liczby pierwszorzędne poniżej i do 5 to 2, 3 i 5. Z powodu 2 liczby, które powinny zostać usunięte z listy wszystkich liczb według wielokrotności, to: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22 i 24. Z powodu 3 liczby, które powinny zostać usunięte z listy przez wielokrotności to: 6, 9, 12, 15, 18, 21 i 24. Z powodu 5 liczby, które powinny być usuwane przez wielokrotności to: 10, 15, 20 i 25.

Według wszystkich wielokrotności usunięcia są następujące:

2: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24

3: 6, 9, 12, 15, 18, 21, 24

5: 10, 15, 20, 25

W mnożnikach 6 jest usuwane dwa razy (teoretycznie), 10 jest usuwane dwa razy (teoretycznie), 12 jest usuwane dwa razy (teoretycznie), 15 jest usuwane dwa razy (teoretycznie), 20 jest usuwane dwa razy (w cle. teoria) i 24 jest usuwane dwa razy (teoretycznie).

Jeśli jednak z powodu 3 usunięcie rozpoczyna się od 3 x 3 = 9, wówczas 6 jest usuwane tylko raz. Jeśli z powodu 5 usunięcie rozpoczyna się od 5 x 5 = 25, wówczas usunięcie 10, 15 i 20. Jednak usunięcie 12, 18 i 24 jest nadal wykonywane dwa razy na liczbę. Mimo to byłaby pewna zaleta, ponieważ pominięto cztery powtarzane operacje usuwania (dla 6, 10, 15 i 20). Poprawia to wydajność (złożoność czasu). Po tym usunięcia będą:

2: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24

3: 9, 12, 15, 18, 21, 24

5: 25

Liczby 6, 10, 15 i 20 zostały usunięte raz, zamiast dwa razy. Liczby, każde z 12, 18 i 24. Na razie nic nie można zrobić, aby usunąć 12, 18 i 24 tylko raz.

Sytuacje dla liczb 36 i 37 lub dowolnej innej liczby większej niż 1 są podobnie wyjaśnione.

Unikanie redundancji

Po prostu usuwając wielokrotności liczb pierwszych z 2 do wartości całkowitej √n, uzyskuje się wymagany zestaw liczb pierwszych. Wydajność można poprawić, usuwając wielokrotności liczb pierwszych, zaczynając od kwadratu liczby pierwszej (i²) aż do wartości liczby całkowitej √n, jak sugerowano wcześniej. Pomija to niektóre operacje usuwania liczb. Zmniejszenie całkowitej liczby operacji. Sito eratostenes odbywa się w tym drugim podejściu.

Algorytm siwa z eratostenes

Algorytm zaczyna się od wykonania indeksowanego wektora o zerowej długości, który wynosi n+1. Każdy element tego wektora jest inicjowany do logicznej, prawdziwy, z wyjątkiem pierwszego i drugiego elementu dla indeksu 0 i indeksu 1, które są inicjowane do fałszywych. W przypadku tego wektora indeks 2 odpowiada liczbie (Prime) 2; Indeks 3 odpowiada liczbie (Prime) 3; Indeks 4 odpowiada liczbie 4; i tak dalej. Ponieważ wektor wynosi zero A wskaźnik oparty, długość musi wynosić n+1, aby ostatni indeks odpowiada n.

Numer indeksu dla tej listy wektorów, który musi zostać usunięty, nie jest usuwany sam: Wartość numeru indeksu jest fałszywa, aby wskazać usunięcie. To znaczy element otrzymuje fałszywą wartość. Tak więc, jeśli liczba (indeks) musi zostać usunięta z listy (wektor) więcej niż raz, wartość indeksu jest fałszywa więcej niż raz.

Na końcu indeksy dla elementów wektora, których wartości pozostały prawdziwe, są odczytane jako liczby pierwszorzędne.

Wcześniej wielokrotności wskaźników pierwotnych zaczynających się od kwadratu pierwszego indeksu (i²) Do wartości liczby całkowitej √n są oznaczone jako fałszywe.

Kodowanie C ++

Program w C ++ powinien zacząć od następujących:

#włączać
#włączać
za pomocą przestrzeni nazw Std;

Sito funkcji Eratosthenes jest następujące:

wektor sive (int n)
wektor sito (n+1, prawda);
sive [0] = false;
sive [1] = false;
int i = 2;
While (i * i <= n)
if (sieve [i] == true) // jeśli i jest liczbą pierwszą
int j = i * i;
While (j <= n) //marking multiples with false
sive [j] = false;
j = j + i; // zwiększaj wielokrotność


i = i + 1; // normalny przyrost pętli zewnętrznej, o 1

Sito Return;

Przeczytaj komentarze kodu. Nazwa funkcji to sive (). Zwracany wektor, po tym, jak wszystkie wielokrotności są oznaczone jako fałszywe, jest również nazywane sito. Odpowiednia główna funkcja C ++ dla tego kodu to:

int main (int argc, char ** argv)

wektor vtr = sito (37);
dla (int i = 0; iif (vtr [i] == true)
Cout << i << ";
Cout << endl;
powrót 0;

Dzięki temu kodowi wyjście jest następujące:

2 3 5 7 11 13 17 19 23 29 31 37

Złożoność czasu dla tej funkcji to O (log log n).

Wniosek

Algorytm zaczyna się od wykonania indeksowanego wektora opartego na zerowej długości N+1. Każdy element tego wektora jest inicjowany do logicznej, prawdziwy, z wyjątkiem pierwszego i drugiego elementu dla indeksu 0 i indeksu 1, które są inicjowane do fałszywych. W przypadku tego wektora każdy indeks ma wiele odsetek. Ponieważ wektor jest indeksowany zero, długość musi wynosić n+1, aby ostatni indeks n wynosi n.

Wartość liczby, która jest indeksem, jest fałszywa, aby wskazać usunięcie. To znaczy element otrzymuje fałszywą wartość.

Na końcu indeksy dla elementów wektora, których wartości pozostały prawdziwe, są odczytane jako liczby pierwszorzędne.

Wcześniej wielokrotności wskaźników pierwszych od kwadratu wskaźnika pierwszego do wartości liczb całkowitych √n są oznaczone jako fałszywe.