obrazek

Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych.
Autor artykułu: mgr Jerzy Wałaszek, wersja1.0

obrazek

Pomoce:

Instalacja Code Blocks i tworzenie projektu aplikacji konsoli.
System uzupełnień do podstawy - U2
Wprowadzenie do języka C++, strumienie i zmienne
Komputer podejmuje decyzje
Pętle warunkowe
Pętla iteracyjna
Wprowadzenie do algorytmów, algorytm Euklidesa

Generacja liczb pierwszych

Liczba pierwsza (ang. primary number) jest liczbą naturalną, która posiada dokładnie dwa różne podzielniki - 1 i siebie samą.

Liczba 1 nie jest pierwszą, ponieważ dzieli się tylko przez 1, a nie posiada drugiego podzielnika różnego od 1. Przykłady liczb pierwszych:

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 ...

Liczby pierwsze maja olbrzymie zastosowanie we współczesnej informatyce. Na nich opierają się zaawansowane systemy szyfrujące, używane przez banki, służby państwowe i wojsko. Dlatego umiejętność sprawdzania pierwszości liczby oraz generacji liczb pierwszych jest podstawową umiejętnością każdego informatyka.

Dowód Euklidesa na nieskończoność zbioru liczb pierwszych

Zbiór liczb pierwszych jest zbiorem nieskończonym. Oznacza to, że dla dowolnie dużej liczby naturalnej zawsze znajdziemy liczbę pierwszą, która jest od niej większa. Nieskończoność tego zbioru udowodnił grecki matematyk Euklides. Zastosował on dowód przez sprowadzenie do sprzeczności.

Załóżmy, że zbiór liczb pierwszych P jest zbiorem skończonym i zawiera n różnych liczb pierwszych:

obrazek

Euklides tworzy liczbę E (zwaną liczbą Euklidesa) wg następującego wzoru:

obrazek

Liczby E nie dzieli żadna z liczb należących do zbioru P - zawsze zostanie reszta 1:

obrazek

Dzieje się tak dlatego, że E jest sumą dwóch składników - iloczynu wszystkich liczb pierwszych ze zbioru P oraz 1. Iloczyn jest podzielny przez swój dowolny składnik. Wynikiem jest iloczyn liczb ze zbioru P, w którym brak tego składnika. Natomiast 1 nie dzieli się przez żadną z tych liczb i zostaje jako reszta.

Wynikają z tego dwa wnioski:

Liczba E nie jest podzielna przez żadną z liczb różną od 1 i siebie samej - zatem jest nową liczbą pierwszą, której nie ma w zbiorze P.
Liczba E jest podzielna przez liczbę pierwszą, której nie ma w zbiorze P, ponieważ te liczby E nie dzielą.

Trzeciej możliwości nie ma. W obu możliwych przypadkach dostajemy nową liczbę pierwszą, której zbiór P nie zawiera. Przeczy to założeniu, że zbiór P zawierał wszystkie liczby pierwsze. Skoro tak, zbiór liczb pierwszych nie może być zbiorem skończonym.

Generacja liczb pierwszych przez sprawdzanie podzielności

Podana wyżej definicja liczby pierwszej jest dla nas niewygodna. Zapiszmy w postacie równoważnej:

Liczba pierwsza p, p > 2, jest liczbą niepodzielną przez żadną z liczb należących do przedziału od 2 do p-1.

Ta druga definicja daje nam wskazówkę, jak szukać liczb pierwszych. Dla danej liczby p wystarczy sprawdzić, czy dzieli się bez reszty przez jakąś liczbę z przedziału od 2 do p-1. Jeśli tak, to p nie jest liczbą pierwszą. Jeśli żadna z liczb z przedziału od 2 do p-1 nie dzieli liczby p, p jest liczba pierwszą.

Algorytm sprawdzania, czy liczba p jest liczbą pierwszą

Wejście:

p - sprawdzana liczba naturalna

Wyjście:

t = true, liczba p jest liczbą pierwszą
t = false, liczba p nie jest liczbą pierwszą

Zmienne pomocnicze:

i - kolejne dzielniki naturalne dla liczby p

Krok 1:	t ← true	; zakładamy sukces
Krok 2:	i ← 2	; pierwszy dzielnik
Krok 3:	Jeśli i ≥ p, to zakończ	; sprawdzamy, czy dzielnik wciąż jest w zakresie od 2 do p-1
Krok 4:	Jeśli p nie dzieli się przez i, to idź do kroku 7	; przechodzimy do wyznaczenia kolejnego podzielnika
Krok 5:	t ← false	; p jest podzielne, zatem nie jest pierwsze
Krok 6:	Zakończ
Krok 7:	i ← i + 1	; wyznaczamy kolejny dzielnik
Krok 8:	Idź do kroku 3	; kontynuujemy sprawdzanie podzielności

obrazek

Poniższy program wykorzystuje podany algorytm do generacji n liczb pierwszych.

// Generacja n liczb pierwszych
// (C)2010 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

int main()
{
    int n,i,p,lp;
    bool t;

    cin >> n;

    lp = 0;
    p = 2;
    
    while(lp < n)
    {
        t = true;
        for(i = 2; i < p; i++)
            if(p % i == 0)
            {
                t = false;
                break;
            }

        if(t)
        {
            cout << p << " ";
            lp++;
        }
        p++;
    }

    cout << endl;

    return 0;
}

Ulepszenie algorytmu generacji liczb pierwszych przez sprawdzanie podzielności

Podany powyżej algorytm, chociaż poprawnie działa, nie jest zbytnio efektywny. Aby stwierdzić, czy liczba p jest pierwsza, musi on wykonać p-3 dzieleń próbnych. Jeśli p jest duże, to liczba dzieleń jest równie duża. Wykonanie algorytmu zajmuje długi czas. Zastanówmy się, czy nie możemy go ulepszyć.

Jeśli liczba p jest liczbą złożoną (a zatem nie jest liczbą pierwszą), to można ją zapisać w postaci iloczynu dwóch liczb naturalnych a i b, które obie są różne od liczby p:

obrazek

Z tych dwóch liczb a i b wystarczy znaleźć tylko jedną, aby wykluczyć pierwszość liczby p. Mamy dwa możliwe przypadki:

Oba dzielniki są równe:

obrazek

Oba dzielniki są różne:

obrazek

Widzimy, że w obu przypadkach jeden z dzielników występuje w przedziale od 2 do pierwiastka z p. Nie może się tak zdarzyć, że oba dzielniki a i b są większe od pierwiastka z p, gdyż wtedy ich iloczyn byłby większy od p. Zatem w celu znalezienia możliwego dzielnika wystarczy przeszukać przedział od 2 do pierwiastka z p. To bardzo duże usprawnienie. Poprzednio, aby sprawdzić, czy liczba p równa około milion jest liczbą pierwszą, należało wykonać około milion dzieleń. Teraz tych dzieleń jest około tysiąc - czyli tysiąc razy mniej. Im większa liczba p, tym zysk mamy większy. Jeśli same liczby a i b są złożone, to nic nie szkodzi - wtedy ich dzielniki są od nich mniejsze i tym bardziej wpadają w nasz przedział.

Algorytm sprawdzania, czy liczba p jest liczbą pierwszą - wersja ulepszona nr 1

Wejście:

p - sprawdzana liczba naturalna

Wyjście:

t = true, liczba p jest liczbą pierwszą
t = false, liczba p nie jest liczbą pierwszą

Zmienne pomocnicze:

g - pierwiastek całkowity z p
i - kolejne dzielniki naturalne dla liczby p

Krok 1:	t ← true	; zakładamy sukces
Krok 2:	g ← \|√p\|	; obliczamy pierwiastek całkowity z p
Krok 3:	i ← 2	; pierwszy dzielnik
Krok 4:	Jeśli i > g, to zakończ	; sprawdzamy, czy dzielnik wciąż jest w zakresie od 2 do pierwiastka z p
Krok 5:	Jeśli p nie dzieli się przez i, to idź do kroku 8	; przechodzimy do wyznaczenia następnego podzielnika
Krok 6:	t ← false	; p jest podzielne, zatem nie jest pierwsze
Krok 7:	Zakończ
Krok 8:	i ← i + 1	; wyznaczamy kolejny dzielnik
Krok 9:	Idź do kroku 4	; kontynuujemy sprawdzanie podzielności

Wyliczenie pierwiastka kwadratowego wymaga funkcji sqrt(x). Dostęp do tej funkcji otrzymamy po dołączeniu pliku nagłówkowego cmath.

// Generacja n liczb pierwszych
// (C)2010 I LO w Tarnowie
//------------------------

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int n,i,p,lp,g;
    bool t;

    cin >> n;

    lp = 0;
    p = 2;
    
    while(lp < n)
    {
        t = true;
        g = sqrt(p);
        for(i = 2; i <= g; i++)
            if(p % i == 0)
            {
                t = false;
                break;
            }

        if(t)
        {
            cout << p << " ";
            lp++;
        }
        p++;
    }

    cout << endl;

    return 0;
}

Jak widzimy, zmiany są bardzo niewielkie, a zysk ogromny - nowy program działa dużo szybciej od poprzedniego.

Kolejne przyspieszenie pracy algorytmu uzyskamy ograniczając dalej podzielniki. Na początku algorytmu sprawdzamy, czy badana liczba jest podzielna przez 2. Jeśli tak, to nie jest pierwsza. Jeśli nie, to możemy dalej wyeliminować podzielniki parzyste. Zredukuje nam to ich liczbę o połowę. Badane liczby p muszą być większe od 2. Liczba 2 jest jedyną liczbą pierwszą podzielną przez 2.

Algorytm sprawdzania, czy liczba p jest liczbą pierwszą - wersja ulepszona nr 2

Wejście:

p - sprawdzana liczba naturalna, p > 2

Wyjście:

t = true, liczba p jest liczbą pierwszą
t = false, liczba p nie jest liczbą pierwszą

Zmienne pomocnicze:

g - pierwiastek całkowity z p
i - kolejne dzielniki nieparzyste dla liczby p

Krok 1:	t ← true	; zakładamy sukces
Krok 2:	Jeśli p dzieli 2, to idź do kroku 7	; eliminujemy liczby podzielne przez 2
Krok 3:	g ← \|√p\|	; obliczamy pierwiastek całkowity z p
Krok 4:	i ← 3	; pierwszy dzielnik nieparzysty
Krok 5:	Jeśli i > g, to zakończ	; sprawdzamy, czy dzielnik wciąż jest w zakresie od 2 do pierwiastka z p
Krok 6:	Jeśli p nie dzieli się przez i, to idź do kroku 9	; przechodzimy do wyznaczenia następnego podzielnika
Krok 7:	t ← false	; p jest podzielne, zatem nie jest pierwsze
Krok 8:	Zakończ
Krok 9:	i ← i + 2	; wyznaczamy kolejny dzielnik nieparzysty
Krok 10:	Idź do kroku 4	; kontynuujemy sprawdzanie podzielności

// Generacja n liczb pierwszych
// (C)2010 I LO w Tarnowie
//------------------------

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int n,i,p,lp,g;
    bool t;

    cin >> n;

    lp = 0;
    p = 2;
    
    while(lp < n)
    {
        t = true;
        if(p > 2)
        {
            if(p % 2)
            {
                g = sqrt(p);
                for(i = 3; i <= g; i += 2)
                    if(p % i == 0)
                    {
                        t = false;
                        break;
                    }
            }
            else t = false;
        }

        if(t)
        {
            cout << p << " ";
            lp++;
        }
        p++;
    }

    cout << endl;

    return 0;
}

Kolejne ulepszenie dotyczy nie samego algorytmu sprawdzania pierwszości liczby, lecz programu ich generacji. Wszystkie liczby pierwsze oprócz 2 i 3 są postaci:

obrazek

Wyjaśnienie tego faktu jest dosyć proste. Pozostałe liczby są postaci:

obrazek

Są one podzielne przez 2 lub 3. Zatem nie mogą być liczbami pierwszymi. Tak wygenerowane liczby sprawdzamy podzielnikami nieparzystymi począwszy od 5 do pierwiastka z p. Dzięki temu rozwiązaniu zmniejszymy do ¹/₃liczbę testowanych na pierwszość liczb.

// Generacja n liczb pierwszych począwszy od 5
// (C)2010 I LO w Tarnowie
//------------------------

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int n,i,p,lp,g,k,d;
    bool t;

    cin >> n;

    lp = 0;
    k = 1; d = -1;
    
    while(lp < n)
    {
        t = true;
        p = 6 * k + d;
        g = sqrt(p);
        for(i = 5; i <= g; i += 2)
            if(p % i == 0)
            {
                t = false;
                break;
            }
        if(t)
        {
            cout << p << " ";
            lp++;
        }
        d = -d;
        if(d == -1) k++;
    }

    cout << endl;

    return 0;
}

Ostatnia modyfikacja dotyczy podzielników. Skoro tworzymy liczby postaci 6k±1, to takie liczby nie dzielą się przez ani przez 2, ani przez 3. Zatem podzielniki również możemy tworzyć w podobny sposób, jak tworzymy liczby p - ze wzoru 6k'±1, gdzie k' jest kolejno równe 1,2,... Oczywiście musi to być inna zmienna od k wykorzystywanego do tworzenia p.

// Generacja n liczb pierwszych począwszy od 5
// (C)2010 I LO w Tarnowie
//------------------------

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int n,i,p,lp,g,k,d,kp,dp;
    bool t;

    cin >> n;

    lp = 0;
    k = 1; d = -1;
    
    while(lp < n)
    {
        t = true;
        p = 6 * k + d;
        g = sqrt(p);

        kp = 1; dp = -1; i = 5;

        while(i <= g)
        {  
            if(p % i == 0)
            {
                t = false;
                break;
            }
            dp = -dp;
            if(dp == -1) kp++;
            i = 6 * kp + dp;
        }

        if(t)
        {
            cout << p << " ";
            lp++;
        }
        d = -d;
        if(d == -1) k++;
    }

    cout << endl;

    return 0;
}

Zmodyfikuj podany program, tak aby nie generował zadanej ilości liczb pierwszych, lecz wszystkie liczby pierwsze w zadanym przedziale <a,b>, gdzie a > 4, a < b.

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

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

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe