Wyznaczanie liczb pierwszych

 

Generacja liczb pierwszych

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

WYZNACZANIE LICZB PIERWSZYCH SPOSOBEM KLASYCZNYM

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:

 

 

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

 

 

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

 

 

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

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

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
  

 

Program wykorzystujący podany algorytm do generacji n  liczb pierwszych.

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

30 tysięcy wyrazów w 35.828sekund. Jest wolniejszy o 
22.399 sekund od ulepszonej wersji.

Ulepszenie algorytmu generacji liczb pierwszych przez sprawdzanie podzielności
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:
 
 
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:
Oba dzielniki są różne:

Algorytm sprawdzania, czy liczba p jest liczbą pierwszą - wersja ulepszona
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, 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
PROGRAM:
#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;
} 

30tysięcy wyrazów w 13.429sekund. Jest o 22.399sekund
szybszy od zwykłego algorytmu.