Matura - programowanie w C++

Na przykład, liczba 6 posiada 4 różne podzielniki: 1, 2, 3, 6. Liczba 4 nie jest podzielnikiem liczby 6, ponieważ:

Tak samo liczba 5 nie jest podzielnikiem liczby 6:

Liczba 1 nie jest liczbą pierwszą, ponieważ ma tylko 1 podzielnik: 1, a nie dwa różne.

Liczba 2 jest początkową liczbą pierwszą, ma dokładnie dwa podzielniki różne: 1 i 2.

Liczba 3 ma dokładnie dwa podzielniki: 1 i 3, jest zatem pierwsza.

Liczba 4 nie jes liczbą pierwszą, ponieważ posiada 3 podzielniki: 1, 2 i 4.

Oto kilka początkowych liczb pierwszych:

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

Ciąg liczb pierwszych jest nieskończony, czyli nie ma największej liczby pierwszej. Dowód pochodzi od Euklidesa i jest następujący:

Do zapamiętania:

• Definicja liczby pierwszej.
• Dowód Euklidesa nieskończoności zbioru liczb pierwszych.

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

// 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;
}

// 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;
}

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

// 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;
}

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:

1. Oba dzielniki m i n są równe:
   
   
    
2. 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.
   
   
    
3. 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

// 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;
}

Podsumujmy czasy wykonań:

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.

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

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

// 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;
}

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.

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:

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

Algorytm nr 2: Sito Eratostenesa

// 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;
}

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:

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:

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

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

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:

Przechodzimy do kolejnej liczby w tablicy, czyli do 5:

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

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

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:

Przechodzimy do następnej liczby: 7:

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

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

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

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

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):

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

// 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;
}

Do zapamiętania:

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