Materiały do matury z informatyki

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.

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

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.

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.

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.

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.

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