Matura: c++ - liczby pierwsze

Wyszukiwanie liczb pierwszych rozpoczniemy od bardzo prymitywnego algorytmu, który bazuje na definicji liczby pierwszej. Ponieważ liczba pierwsza p dzieli się tylko przez 1 i siebie samą, to nie dzieli się przez żadną z liczb od 2 do p - 1 (z wyjątkiem liczby 2, która jest jedyną liczbą pierwszą podzielną przez 2). Będziemy zatem postępować następująco:

Aby sprawdzić, czy liczba p jest liczbą pierwszą, próbujemy ją dzielić przez kolejne liczby od 2 po p - 1. Jeśli żadna z tych liczb nie dzieli p, to p jest pierwsze. W przeciwnym razie p jest złożone.

Algorytm nr 1: Wyszukiwanie liczb pierwszych przez sprawdzanie podzielności

Dane wejściowe: p - liczba naturalna testowana na pierwszość, p > 1

Dane wyjściowe: prawda - liczba p jest pierwsza, fałsz - liczba p jest złożona

Lista kroków:
K01: Dla i = 2,3,...,p - 1,
     wykonuj krok K02
K02:     Jeśli i dzieli p,
         to zakończ z wynikiem fałsz
K03: Zakończ z wynikiem prawda

Kroki K01 i K02 tworzą pętlę, w której sprawdzana jest podzielność testowanej na pierwszość liczby p przez kolejne dzielniki od 2 do p - 1. Jeśli którykolwiek z nich dzieli p, to p nie jest liczbą pierwszą, ponieważ ma dzielnik różny od 1 i od siebie samej. W takim przypadku zwracamy fałsz i kończymy algorytm.

Gdy pętla sprawdzi wszystkie dzielniki od 2 do p - 1 i żaden nie dzieli p, to algorytm przechodzi do kroku K03, gdzie się kończy z wynikiem prawda, czyli p jest liczbą pierwszą.

Poniższy program wykorzystuje ten algorytm do wyznaczenia liczb pierwszych z przedziału [a,b] (a > 1; b ≥ a):

// Liczby pierwsze
// Algorytm nr 1
//----------------

#include <iostream>

using namespace std;

// Zwraca:
// true  - p jest pierwsze
// false - p jest złożone
//------------------------
bool is_prime(unsigned p)
{
    for(unsigned i = 2; i < p; i++)
        if(!(p % i)) return false;
    return true;
}

int main()
{

    cout << "Wyszukiwanie liczb pierwszych" << endl
         << "w zakresie od a do b" << endl
         << "-----------------------------" << endl << endl;
    unsigned a, b;
    cout << "a = "; cin >> a; // Odczytujemy zakres
    cout << "b = "; cin >> b; // poszukiwania
    cout << endl;

    // Wypisujemy znalezione liczby pierwsze
    if((a > 1) && (b >= a))
        for(unsigned p = a; p <= b; p++)
            if(is_prime(p)) cout << p << " ";

    cout << endl << endl;

    return 0;
}

Wyszukiwanie liczb pierwszych
w zakresie od a do b
-----------------------------

a = 100000000
b = 100000050

100000007 100000037 100000039 100000049

Zwróć uwagę, że im większe liczby, tym dłużej je komputer wyszukuje. Spowodowane to jest tym, iż liczba pierwsza zostaje rozpoznana po wykonaniu wszystkich dzieleń próbnych od 2 do p - 1, a ich liczba rośnie wraz ze wzrostem p.

Ponieważ będziemy ten algorytm stopniowo poprawiać, zmodyfikujemy nieco program tak, aby wyszukiwał liczby pierwsze w zakresie od 1000000000 do 1000000200:

// Liczby pierwsze
// Algorytm nr 1
//----------------

#include <iostream>

using namespace std;

// Zwraca:
// true  - p jest pierwsze
// false - p jest złożone
//------------------------
bool is_prime(unsigned p)
{
    for(unsigned i = 2; i < p; i++)
        if(!(p % i)) return false;
    return true;
}

int main()
{
    unsigned const A = 1000000000;
    unsigned const B = 1000000200;

    // Wypisujemy znalezione liczby pierwsze
    for(unsigned p = A; p <= B; p++)
        if(is_prime(p)) cout << p << " ";

    cout << endl << endl;

    return 0;
}

Uruchom program trzykrotnie i zapisz czasy obliczeń, które są podawane w oknie konsoli przy zakończeniu programu. Za każdym razem czasy będą się nieco różnić, ponieważ w tle komputer wykonuje również procedury systemowe i te zadania nieco opóźniają nasz program. Z tych 3 czasów wybierz najmniejszy. Otrzymasz przybliżony czas wyszukiwania liczb pierwszych w przedziale [1000000000, 1000000200] na swoim komputerze. U mnie czas ten wyniósł: 41,276 s.

Uruchomienie	Czas
#1	41,314 s
#2	41,276 s
#3	41,286 s

Ulepszanie algorytmu będzie polegało na eliminacji liczby dzieleń, ponieważ ich jest najwięcej przy dużych liczbach i wpływają one bezpośrednio na czas obliczeń. Najpierw usuniemy dzielniki parzyste. Jedyną liczbą pierwszą parzystą jest liczba 2. Zatem algorytm powinien sprawdzić, czy testowana liczba jest równa 2. Jeśli tak, to algorytm kończy działanie z wynikiem prawda. Jeśli liczba nie jest równa 2, to sprawdzamy, czy dzieli się przez 2. Jeśli tak, to nie jest pierwsza, ponieważ jest różna od 2, a 2 jest jedyną liczbą pierwszą podzielną przez 2, a tę już wyeliminowaliśmy. W tym przypadku algorytm kończy pracę z wynikiem fałsz. Jeśli liczba nie dzieli się przez 2, to również nie dzieli się przez 4, 6, 8, ... ,czyli przez liczby parzyste. Pozostaje nam zatem sprawdzenie podziału przez liczby nieparzyste. W ten sposób zredukowaliśmy liczbę podzielników o połowę.

Algorytm nr 2: Wyszukiwanie liczb pierwszych przez sprawdzanie podzielności

Dane wejściowe: p - liczba naturalna testowana na pierwszość, p > 1

Dane wyjściowe: prawda - liczba p jest pierwsza, fałsz - liczba p jest złożona

Lista kroków:
K01: Jeśli p = 2,
     to zakończ z wynikiem prawda
K02: Jeśli p dzieli się przez 2,
     to zakończ z wynikiem fałsz
K03: i ← 3
K04: Dopóki i < p:
     wykonuj kroki K05 ... K06
K05:     Jeśli p dzieli się przez i,
         to zakończ z wynikiem fałsz
K06:     i ← i + 2
K07: Zakończ z wynikiem prawda

Program C++:

// Liczby pierwsze
// Algorytm nr 2
//----------------

#include <iostream>

using namespace std;

// Zwraca:
// true  - p jest pierwsze
// false - p jest złożone
//------------------------
bool is_prime(unsigned p)
{
    if(p == 2)   return true;
    if(!(p % 2)) return false;
    for(unsigned i = 3; i < p; i += 2)
        if(!(p % i)) return false;
    return true;
}

int main()
{
    unsigned const A = 1000000000;
    unsigned const B = 1000000200;

    // Wypisujemy znalezione liczby pierwsze
    for(unsigned p = A; p <= B; p++)
        if(is_prime(p)) cout << p << " ";

    cout << endl << endl;

    return 0;
}

Uruchom program 3 razy i zapisz czasy działania. Z tych 3 czasów wybierz najmniejszy.

Uruchomienie	Czas
#1	20,648 s
#2	20,637 s
#3	20,612 s

U mnie czas wyniósł 20,612 s. Poprzedni czas był równy 41,276 s. Jak widzisz ulepszony algorytm wykonuje się o połowę krócej (ponieważ zredukowaliśmy o połowę liczbę dzieleń). W informatyce jest zwykle tak, iż proste algorytmy mają długi czas rozwiązywania problemu, natomiast algorytmy skomplikowane wykonują się szybciej.

Trzeci algorytm musi sięgnąć do matematyki, aby jeszcze bardziej zredukować liczbę wykonywanych dzieleń.

Jeśli liczba p jest liczbą złożoną (czyli nie jest pierwsza), to można ją przedstawić jako iloczyn dwóch liczb naturalnych będących jej dzielnikami różnymi od 1 i od niej samej:

Zastanówmy się, jakie wartości mogą te dzielniki przyjmować. Mamy dwa możliwe przypadki:

Oba dzielniki m i n są równe:
Oba dzielniki m i n są różne. W takim przypadku jeden jest mniejszy, a drugi większy. Mniejszy dzielnik musi być mniejszy od pierwiastka kwadratowego z p, bo gdyby oba dzielniki były większe od pierwiastka kwadratowego z p, to ich iloczyn stałby się większy od samego p, co przeczyłoby założeniu.
Trzeciej możliwości nie ma.

Jeśli wykluczymy dzielnik 2, to liczba p jest pierwsza, jeśli nie posiada dzielnika nieparzystego w przedziale od 3 do pierwiastka kwadratowego z p. Nie trzeba zatem przeszukiwać całego przedziału od 3 do p -1 w poszukiwaniu dzielnika. Jaka stąd korzyść? Dla liczby z zakresu miliona algorytm nr 2 musiał wykonać około pół miliona dzieleń, aby potwierdzić jej pierwszość. Teraz tych dzieleń jest około pierwiastek kwadratowy z miliona przez 2, czyli około 500 (2 tysiące razy mniej)!

Algorytm nr 3: Wyszukiwanie liczb pierwszych przez sprawdzanie podzielności

Dane wejściowe: p - liczba naturalna testowana na pierwszość, p > 1

Dane wyjściowe: prawda - liczba p jest pierwsza, fałsz - liczba p jest złożona

Lista kroków:
K01: Jeśli p = 2,
     to zakończ z wynikiem prawda
K02: Jeśli p dzieli się przez 2,
     to zakończ z wynikiem fałsz
K03: g ← pierwiastek z p
K04: i = 3
K05: Dopóki i ≤ g:
     wykonuj kroki K06 ... K07
K06:     Jeśli p dzieli się przez i,
         to zakończ z wynikiem fałsz
K07:     i ← i + 2
K08: Zakończ z wynikiem prawda

// Liczby pierwsze
// Algorytm nr 3
//----------------

#include <iostream>
#include <cmath>

using namespace std;

// Zwraca:
// true  - p jest pierwsze
// false - p jest złożone
//------------------------
bool is_prime(unsigned p)
{
    if(p == 2) return true;
    if(!(p % 2)) return false;
    unsigned g = sqrt(p);
    for(unsigned i = 3; i <= g; i += 2)
        if(!(p % i)) return false;
    return true;
}

int main()
{
    unsigned const A = 1000000000;
    unsigned const B = 1000000200;

    // Wypisujemy znalezione liczby pierwsze
    for(unsigned p = A; p <= B; p++)
        if(is_prime(p)) cout << p << " ";

    cout << endl << endl;

    return 0;
}

Do programu dołączyliśmy plik nagłówkowy cmath, w którym znajdują się definicje funkcji matematycznych - potrzebujemy funkcji pierwiastka kwadratowego – sqrt( ).

Program uruchom 3 razy, zanotuj czasy wykonań i wybierz najmniejszy.

Uruchomienie	Czas
#1	0,037 s
#2	0,032 s
#3	0,022 s

U mnie czas wyniósł 0,022 sekundy, czyli praktycznie natychmiast.

Podsumujmy czasy wykonań:

Algorytm	Czas wykonania	Porównanie
#1	40,046 s	Najwolniejszy
#2	20,612 s
#3	0,022 s	Najszybszy

Istnieją jeszcze szybsze metody sprawdzania pierwszości liczby, które znajdują zastosowanie dla naprawdę dużych liczb.

Do zapamiętania:

Algorytm wyszukiwania liczb pierwszych przez sprawdzanie podzielności: podstawowy, z dzielnikami nieparzystymi, z ograniczeniem do pierwiastka.
Zasada: skomplikowany algorytm działa zwykle szybciej od prostego.

Na początek: podrozdziału strony

Sito Eratostenesa

Grecki matematyk Eratostenes podszedł do problemu wyszukiwania liczb pierwszych w inny sposób: skoro liczby pierwsze nie są podzielne przez żadne liczby większe od 1 i mniejsze od nich samych, to aby je znaleźć w zbiorze początkowych liczb naturalnych od 2 do n, należy wyrzucić z tego zbioru wszystkie wielokrotności kolejnych liczb. To, co zostanie w zbiorze, będzie liczbami pierwszymi. Metoda ta nosi nazwę Sita Eratostenesa (ang. Sieve of Eratosthenes).

Zobaczmy na prostym przykładzie, jak to działa:

Mamy zbiór początkowych liczb naturalnych od 2 do 50:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2021 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

Bierzemy pierwszą liczbę 2, zostawiamy ją w zbiorze, lecz wyrzucamy z niego wszystkie wielokrotności 2:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

Oprócz początkowej liczby 2 w zbiorze zostały tylko liczby nieparzyste, czyli niepodzielne przez 2. Przechodzimy do liczby 3 i powtarzamy to samo: liczbę 3 zostawiamy w zbiorze, lecz wyrzucamy z niego wszystkie wielokrotności 3:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

Liczbę 4 pomijamy, ponieważ została już wyrzucona ze zbioru jako wielokrotność liczby 2. Następną liczbą jest zatem 5. Powtarzamy całą procedurę: liczbę 5 pozostawiamy, lecz ze zbioru wyrzucamy wszystkie jej wielokrotności:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

Kolejną liczbą będzie 7, ponieważ 6 zostało już wyrzucone jako wielokrotność 2. Powtarzamy całą procedurę:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

Kontynuujemy z pozostałymi liczbami do końca zbioru. W efekcie w zbiorze pozostały liczby pierwsze, które nie są wielokrotnościami mniejszych liczb.

Pozostaje pewien problem techniczny: jak wyrzucać liczby ze zbioru. Należy przyjąć wygodną strukturę danych. Będzie to tablica o indeksach od 0 do n. Komórki tablicy będą danymi typu bool, czyli będą mogły przyjmować wartości false lub true. Liczby będą odpowiadały indeksom tablicy. Jeśli komórka o indeksie x ma wartość true, to liczba x jest w zbiorze. Jeśli komórka o indeksie x ma wartość false, to liczby x nie ma w zbiorze. Zatem wyrzucanie liczby x ze zbioru będzie sprowadzało się do wpisania wartości false do komórki tablicy o indeksie x. Gdy wyrzucanie wielokrotności zostanie zakończone, przeglądamy kolejne komórki tablicy i wypisujemy ich indeksy, jeśli zawierają true. Na początku algorytmu wpisujemy do każdej komórki tablicy wartość true, co oznacza, że w zbiorze są wszystkie liczby. Komórki o indeksach 0 i 1 ignorujemy.

Algorytm nr 1: Sito Eratostenesa

Dane wejściowe: n – maksymalna liczba zbioru od 0 do n, w którym poszukujemy liczb pierwszych

Dane wyjściowe: liczby pierwsze zawarte w zbiorze od 0 no n.

Lista kroków:
K01: Czytaj n
K02: Utwórz tablicę T typu bool
     o n+1 komórkach
K03: Dla i = 2,3,...,n:
     wykonuj: T[i] ← true
K04: Dla i = 2,3,...,n - 1:
     wykonuj kroki K05...K09
K05:     Jeśli T[i] = false,
         to następny obieg pętli K04
K06:     w  ←  i + i
K07:     Dopóki w ≤ n:
         wykonuj kroki K08...K09
K08:         T[w] ← false
K09:         w  ← w + i
K10: Dla i = 2,3,...,n:
     wykonuj krok K11
K11:     Jeśli T[i] = true,
         to pisz i
K12: Zakończ

W kroku 2 tworzymy tablicę logiczną T o n+1 komórkach. Indeksy są od 0 do n.
W kroku 3 wypełniamy tablicę T wartością logiczną true. Komórki o indeksach 0 i 1 pomijamy.
Pętla K4...K9 wyrzuca z tablicy liczby będące wielokrotnościami i. Pierwsza wielokrotność to 2i (i + i).
Pętla K10...K11 przegląda tablicę i wypisuje indeksy tych komórek, które zachowały wartość true, czyli te liczby, które algorytm sita Eratostenesa nie wyrzucił ze zbioru

Program C++:

// Sito Eratostenesa
// Algorytm nr 1
//------------------

#include <iostream>

using namespace std;

int main()
{
    int n,i,w;

    cout << "Sito Eratostenesa" << endl
         << "-----------------" << endl << endl
         << "n = "; cin >> n;
    cout << endl;

    // Tworzymy dynamicznie tablicę logiczną

    bool * T = new bool[n + 1];

    // Tablicę wypełniamy wartością true

    for(i = 2; i <= n; i++) T[i] = true;

    // Sito

    for(i = 2; i <= n; i++)
        if(T[i])
            for(w = i + i; w <= n; w += i)
                T[w] = false;

    // Wypisujemy liczby pierwsze

    for(i = 2; i <= n; i++)
        if(T[i]) cout << i << " ";

    cout << endl << endl;

    // usuwamy tablicę dynamiczną

    delete [] T;

    return 0;
}

Sito Eratostenesa
-----------------

n = 50

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

Podobnie jak w algorytmie wyszukiwania liczb pierwszych przez sprawdzanie podzielności, również w algorytmie sita Eratostenesa można zastosować wiele usprawnień, które zwiększą szybkość działania, chociaż sito Eratostenesa działa i tak bardzo szybko.

Zwróć uwagę, iż podstawowy algorytm wielokrotnie wyrzuca ze zbioru te same wielokrotności. Pierwszą niewyrzuconą wielokrotnością jest kwadrat liczby. Wszystkie wielokrotności mniejsze zostały już wyrzucone, ponieważ są wielokrotnościami liczb mniejszych.

2	→	4
3	→	6 9
5	→	10 15 20 25
7	→	14 21 28 35 42 49
11	→	22 33 44 55 66 77 88 99 110 121
13	→	26 39 52 65 78 91 104 117 130 143 156 169

Z drugiej strony jeśli kwadrat liczby jest większy od n, to w zbiorze nie ma już wielokrotności do wyrzucenia i algorytm można zakończyć. Wynikają stąd dwa usprawnienia:

Zbiór przeglądamy od 2 do pierwiastka z n.
Pierwszą wyrzucaną ze zbioru wielokrotnością liczby jest jej kwadrat.

Algorytm nr 2: Sito Eratostenesa

Dane wejściowe: n – maksymalna liczba zbioru od 0 do n, w którym poszukujemy liczb pierwszych

Dane wyjściowe: liczby pierwsze zawarte w zbiorze od 0 no n.

Lista kroków:
K01: Czytaj n
K02: Utwórz tablicę T typu bool
     o n+1 komórkach
K03: Dla i = 2,3,...,n:
     wykonuj: T[i] ← true
K04: g  ←   pierwiastek z n
K05: Dla i = 2,3,...,g:
     wykonuj kroki K06...K10
K06:     Jeśli T[i] = false,
         to następny obieg pętli K05
K07:     w  ←  i · i
K08:     Dopóki w ≤ n:
         wykonuj kroki K09...K10
K09:         T[w] ← false
K10:         w  ← w + i
K11: Dla i = 2,3,...,n:
     wykonuj krok K12
K12:     Jeśli T[i] = true,
         to pisz i
K13: Zakończ

W kroku 2 tworzymy tablicę logiczną T o n+1 komórkach. Indeksy są od 0 do n.
W kroku 3 wypełniamy tablicę T wartością logiczną true. Komórki o indeksach 0 i 1 pomijamy.
W kroku 4 obliczamy granicę przeszukiwania tablicy T.
Pętla K05...K10 wyrzuca z tablicy liczby będące wielokrotnościami i. Pierwsza wielokrotność to i² (i · i).
Pętla K11...K12 przegląda tablicę i wypisuje indeksy tych komórek, które zachowały wartość true, czyli te liczby, które algorytm sita Eratostenesa nie wyrzucił ze zbioru

Program C++:

// Sito Eratostenesa
// Algorytm nr 2
//------------------

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int n,i,w,g;

    cout << "Sito Eratostenesa 2" << endl
         << "-------------------" << endl << endl
         << "n = "; cin >> n;
    cout << endl;

    // Tworzymy dynamicznie tablicę logiczną

    bool * T = new bool[n + 1];

    // Tablicę wypełniamy wartością true

    for(i = 2; i <= n; i++) T[i] = true;

    // Liczymy granicę przetwarzania

    g = sqrt(n);

    // Sito

    for(i = 2; i <= g; i++)
        if(T[i])
            for(w = i * i; w <= n; w += i)
                T[w] = false;

    // Wypisujemy liczby pierwsze

    for(i = 2; i <= n; i++)
        if(T[i]) cout << i << " ";

    cout << endl << endl;

    // usuwamy tablicę dynamiczną

    delete [] T;

    return 0;
}

Sito Eratostenesa 2
-------------------

n = 50

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

Algorytm Sita Eratostenesa wymaga pamięci na tablicę logiczną. Wymagania pamięciowe można zmniejszyć, przechowując w tablicy jedynie liczby nieparzyste (jedyną parzystą liczbą pierwszą jest 2). W tym przypadku indeksy kolejnych komórek tablicy logicznej należy odpowiednio przeliczyć na wartości liczb:

indeks	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	39	30	31	32	33	34	35	36	37	38	39
liczba	3	5	7	9	11	13	15	17	19	21	23	25	27	29	31	33	35	37	39	41	43	45	47	49	51	53	55	57	59	61	63	65	67	69	71	73	75	77	79	81

Wzory przeliczeniowe są następujące:

liczba = 2 · indeks + 3
indeks = (liczba - 3) : 2

Na przykład liczba 49 reprezentowana jest przez komórkę o indeksie: (49 - 3) : 2 = 46 : 2 = 23.

Z kolei komórka o indeksie 36 reprezentuje liczbę: 2 · 36 + 3 = 72 + 3 = 75.

Początek algorytmu jest podobny do poprzedniego: Odczytujemy zakres n (n > 3). Jeśli n jest parzyste, to zmniejszamy je o 1, aby otrzymać ostatnią liczbę nieparzystą w zbiorze. Teraz indeks ostatniej komórki tablicy wyliczamy ze wzoru: (n - 3) : 2. Ilość komórek tablicy będzie równa 1 + (n - 3) : 2. Tworzymy dynamicznie tablicę logiczną o takim rozmiarze i wypełniamy ją wartościami true. Rozpoczynamy od pierwszej komórki tablicy, która reprezentuje liczbę 3:

indeks	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	39	30	31	32	33	34	35	36	37	38	39
liczba	3	5	7	9	11	13	15	17	19	21	23	25	27	29	31	33	35	37	39	41	43	45	47	49	51	53	55	57	59	61	63	65	67	69	71	73	75	77	79	81

Pierwszą wyrzucaną wielokrotnością jest kwadrat 3 = 9:

indeks	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	39	30	31	32	33	34	35	36	37	38	39
liczba	3	5	7	9	11	13	15	17	19	21	23	25	27	29	31	33	35	37	39	41	43	45	47	49	51	53	55	57	59	61	63	65	67	69	71	73	75	77	79	81

Oznaczmy pozycję pierwszej wyrzucanej wielokrotności (czyli kwadratu liczby) przez q₀ = 3. Następnymi wielokrotnościami liczby 3 będą:

indeks	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	39	30	31	32	33	34	35	36	37	38	39
liczba	3	5	7	9	11	13	15	17	19	21	23	25	27	29	31	33	35	37	39	41	43	45	47	49	51	53	55	57	59	61	63	65	67	69	71	73	75	77	79	81

Zauważ, iż wielokrotności te są w naszej tablicy w odstępach co 3. Oznaczmy odstęp przez p₀ = 3.

Zatem wyrzucanie wielokrotności rozpoczynamy na pozycji q₀, którą następnie zwiększamy o p₀, aż osiągniemy koniec tablicy. W ten sposób wyrzucimy liczby podzielne przez 3:

indeks	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	39	30	31	32	33	34	35	36	37	38	39
liczba	3	5	7	9	11	13	15	17	19	21	23	25	27	29	31	33	35	37	39	41	43	45	47	49	51	53	55	57	59	61	63	65	67	69	71	73	75	77	79	81

Przechodzimy do kolejnej liczby w tablicy, czyli do 5:

indeks	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	39	30	31	32	33	34	35	36	37	38	39
liczba	3	5	7	9	11	13	15	17	19	21	23	25	27	29	31	33	35	37	39	41	43	45	47	49	51	53	55	57	59	61	63	65	67	69	71	73	75	77	79	81

Pierwszą wyrzucaną wielokrotnością jest kwadrat 5, czyli 25 na pozycji 11:

indeks	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	39	30	31	32	33	34	35	36	37	38	39
liczba	3	5	7	9	11	13	15	17	19	21	23	25	27	29	31	33	35	37	39	41	43	45	47	49	51	53	55	57	59	61	63	65	67	69	71	73	75	77	79	81

Oznaczmy tę pozycję jako q₁ = 11 = q₀ + 8. Kolejne wyrzucane wielokrotności 5 znajdują się w tablicy w odstępach co 5:

indeks	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	39	30	31	32	33	34	35	36	37	38	39
liczba	3	5	7	9	11	13	15	17	19	21	23	25	27	29	31	33	35	37	39	41	43	45	47	49	51	53	55	57	59	61	63	65	67	69	71	73	75	77	79	81

Oznaczmy p₁ = 5 = p₀ + 2. Wyrzucanie wielokrotności rozpoczynamy na pozycji q₁, którą następnie zwiększamy o p₁, aż osiągniemy koniec tablicy. Z tablicy zostaną wyrzucone liczby nieparzyste podzielne przez 5. Niektóre z nich zostały już wcześniej wyrzucone, ponieważ były również wielokrotnościami 3:

indeks	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	39	30	31	32	33	34	35	36	37	38	39
liczba	3	5	7	9	11	13	15	17	19	21	23	25	27	29	31	33	35	37	39	41	43	45	47	49	51	53	55	57	59	61	63	65	67	69	71	73	75	77	79	81

Przechodzimy do następnej liczby: 7:

indeks	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	39	30	31	32	33	34	35	36	37	38	39
liczba	3	5	7	9	11	13	15	17	19	21	23	25	27	29	31	33	35	37	39	41	43	45	47	49	51	53	55	57	59	61	63	65	67	69	71	73	75	77	79	81

Pierwszą wyrzucaną wielokrotnością będzie kwadrat 7 = 49 na pozycji 23:

indeks	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	39	30	31	32	33	34	35	36	37	38	39
liczba	3	5	7	9	11	13	15	17	19	21	23	25	27	29	31	33	35	37	39	41	43	45	47	49	51	53	55	57	59	61	63	65	67	69	71	73	75	77	79	81

Oznaczmy q₂ = 23 = q₁ + 12. Kolejne wyrzucane wielokrotności są w odstępach co 7 (widzisz już regularność?). Oznaczmy zatem p₂ = 7 = p₁ + 2:

indeks	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	39	30	31	32	33	34	35	36	37	38	39
liczba	3	5	7	9	11	13	15	17	19	21	23	25	27	29	31	33	35	37	39	41	43	45	47	49	51	53	55	57	59	61	63	65	67	69	71	73	75	77	79	81

Wyrzucanie wielokrotności rozpoczynamy na pozycji q₂, którą następnie zwiększamy o p₂, aż osiągniemy koniec tablicy.

indeks	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	39	30	31	32	33	34	35	36	37	38	39
liczba	3	5	7	9	11	13	15	17	19	21	23	25	27	29	31	33	35	37	39	41	43	45	47	49	51	53	55	57	59	61	63	65	67	69	71	73	75	77	79	81

Kolejną liczbą w tablicy jest 9. q₃ = 39 = q₂ + 16, p₃ = 9 = p₂ + 2:

indeks	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	39	30	31	32	33	34	35	36	37	38	39
liczba	3	5	7	9	11	13	15	17	19	21	23	25	27	29	31	33	35	37	39	41	43	45	47	49	51	53	55	57	59	61	63	65	67	69	71	73	75	77	79	81

Liczbę 9 pomijamy, gdyż została ona już wyrzucona z tablicy jako wielokrotność 3. Kolejna liczba 11 kończy algorytm, ponieważ jej kwadrat wychodzi poza tablicę (ostatnią liczbą w tablicy jest 81):

indeks	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	39	30	31	32	33	34	35	36	37	38	39
liczba	3	5	7	9	11	13	15	17	19	21	23	25	27	29	31	33	35	37	39	41	43	45	47	49	51	53	55	57	59	61	63	65	67	69	71	73	75	77	79	81

Odstępy p oraz pozycje początkowe wielokrotności q wyliczamy rekurencyjnie wg wzorów:

Po tych rozważaniach możemy skonstruować algorytm:

Algorytm nr 3: Sito Eratostenesa

Dane wejściowe: n – maksymalna liczba zbioru od 0 do n, w którym poszukujemy liczb pierwszych

Dane wyjściowe: liczby pierwsze zawarte w zbiorze od 0 no n.

Lista kroków:
K01: Czytaj n
K02: Jeśli n jest parzyste,
     to n ← n - 1
K03: r ← 1 + (n - 3) / 2
K04: Twórz dynamicznie tablicę
     logiczną T o r komórkach
K05: Dla i = 0,1,...,r - 1:
     wykonuj T[i] ← true
K06: p ← 3
K07: q ← 3
K08: Dopóki q < r:
     wykonuj kroki K09...K14
K09:     w ← q
K10:    Dopóki w < r:
        wykonuj kroki K11...K12
K11:        T[w] ← false
K12:        w ← w + p
K13:     p ← p + 2
K14:     q ← q + 2 · (p - 1)
K15: Pisz 2
K16: Dla i = 0,1,...,r - 1:
     wykonuj krok K17
K17:     Jeśli T[i] = true,
         to pisz 2 · i + 3
K18: Zakończ

Program C++:

// Sito Eratostenesa
// Algorytm nr 3
//------------------

#include <iostream>

using namespace std;

int main()
{
    int n,i,w,r,p,q;

    cout << "Sito Eratostenesa 3" << endl
         << "-------------------" << endl << endl
         << "n = "; cin >> n;
    cout << endl;

    // Obliczamy rozmiar tablicy dynamicznej

    if(!(n % 2)) n--;
    r = 1 + (n - 3) / 2;

    // Tablica dynamiczna

    bool * T = new bool[r];

    // Tablicę wypełniamy wartościami true

    for(i = 0; i < r; i++) T[i] = true;

    // Sito Eratostenesa

    p = q = 3;

    while(q < r)
    {
        for(w = q; w < r; w += p) T[w] = false;

        p += 2;
        q += 2 * (p - 1);
    }

    // Wypisujemy znalezione liczby pierwsze

    cout << "2 ";
    for(i = 0; i < r; i++)
        if(T[i]) cout << 2 * i + 3 << " ";

    cout << endl << endl;

    delete [] T;

    return 0;
}

Sito Eratostenesa 3
-------------------

n = 50

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

Do zapamiętania:

Zasada działania Sita Eratostenesa
Algorytm nr 1 i 2 (opcjonalnie 3)

Na początek: podrozdziału strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Matura - programowanie w C++

Liczby pierwsze

Definicja liczby pierwszej

Do zapamiętania:

Wyszukiwanie liczb pierwszych

Algorytm nr 1: Wyszukiwanie liczb pierwszych przez sprawdzanie podzielności

Algorytm nr 2: Wyszukiwanie liczb pierwszych przez sprawdzanie podzielności

Algorytm nr 3: Wyszukiwanie liczb pierwszych przez sprawdzanie podzielności

Do zapamiętania:

Sito Eratostenesa

Algorytm nr 1: Sito Eratostenesa

Algorytm nr 2: Sito Eratostenesa

Algorytm nr 3: Sito Eratostenesa

Do zapamiętania: