Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz  

Autor artykułu: mgr Jerzy Wałaszek
Zmodyfikowano 23.03.2023

©2023 mgr Jerzy Wałaszek
I LO w Tarnowie

Materiały do matury z informatyki

Liczby pierwsze

SPIS TREŚCI

Definicja liczby pierwszej

Podzielnik liczby naturalnej a jest taką liczbą naturalną b, iż b dzieli a bez reszty (mowa tutaj jest o dzieleniu całkowitoliczbowym).

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 pierwsza (ang. primary number) jest liczbą naturalną posiadającą dokładnie dwa różne podzielniki: 1 i siebie samą.

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:

Załóżmy, iż zbiór liczb pierwszych P jest skończony i składa się z ciągu n liczb pierwszych pi, i = 1,2,...,n:

Tworzymy liczbę Euklidesa E następująco:

Liczba Euklidesa E jest sumą iloczynu wszystkich liczb pierwszych ze zbioru P i liczby 1. W takiej postaci liczby E nie dzieli żadna z liczb pierwszych ze zbioru P, ponieważ przy podziale zawsze otrzymujemy resztę 1 (uzasadnij to).

Liczba E jest zatem:

  1. nową liczbą pierwszą, ponieważ nie dzieli się przez żadną inną liczbę różną od siebie samej i 1 (uzasadnij to),
  2. liczbą złożoną, podzielną przez liczbę pierwszą, której nie ma w zbiorze P (uzasadnij to).

Trzeciej możliwości nie ma. W każdym z tych dwóch przypadków otrzymujemy nową liczbę pierwszą niezawartą w zbiorze P, co przeczy założeniu, iż zbiór P zawiera wszystkie liczby pierwsze. Wynika stąd, iż zbiór liczb pierwszych jest zbiorem nieskończonym.

Do zapamiętania:

Na początek:  podrozdziału   strony 

Wyszukiwanie liczb pierwszych

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

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

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

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

  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

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:

Na początek:  podrozdziału   strony 

Sito Eratostenesa

xxx
Na początek:  podrozdziału   strony 

P4

xxx
Na początek:  podrozdziału   strony 

P5

xxx
Na początek:  podrozdziału   strony 

P6

xxx
Na początek:  podrozdziału   strony 

P7

xxx
Na początek:  podrozdziału   strony 

P8

xxx
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2023 mgr Jerzy Wałaszek

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.