Matura - programowanie w C++

Zbiór liczb naturalnych (bez liczby 1) można rozłożyć na dwa rozłączne podzbiory: zbiór liczb pierwszych i zbiór liczb złożonych. Liczba pierwsza posiada dokładnie dwa różne dzielniki: 1 i siebie samą. Pozostałe liczby są liczbami złożonymi (ang. composite numbers), które posiadają dodatkowo co najmniej dwa dzielniki oprócz 1 i siebie samych. Na przykład:

8 posiada dzielniki 1, 2, 4, 8
60 posiada dzielniki 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60

Liczby złożone w przedziale od 2 do 100:

4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 98, 99, 100.

Każdą liczbę złożoną da się jednoznacznie (tzn. tylko w dokładnie jeden sposób) przedstawić w postaci iloczynu liczb pierwszych, które są jej dzielnikami. Takie dzielniki nazywamy czynnikami pierwszymi (ang. prime factors). Jest to podstawowe twierdzenie arytmetyki.

Przykład:

60 = 2 · 2 · 3 · 5

Czynniki pierwsze mogą się powtarzać. Takie przedstawienie liczby złożonej w postaci iloczynu liczb pierwszych nazywamy rozkładem liczby na czynniki pierwsze.

Do zapamiętania:

• Liczba złożona.
• Czynnik pierwszy.
• Rozkład na czynniki pierwsze.

Przykład:

288 : 2

=

144

→ 2

144 : 2

 =

 72

→ 2

 72 : 2

=

 36

→ 2

 36 : 2

=

 18

→ 2

 18 : 2

=

  9

→ 2

  9 : 2

: nie dzieli się, nowy dzielnik p = 3

  9 : 3

=

 3

→ 3

  3 : 3

=

 1

→ 3

 i koniec, bo L = 1

    288

=

2 × 2 × 2 × 2 × 2 × 3 × 3

Algorytm nr 1: Rozkład na czynniki pierwsze

p ← 2
dopóki L > 1 wykonuj:
    jeśli L dzieli się przez p to
        pisz p
        L ← L : p
    inaczej
        p ← p + 1

// Rozkład na czynniki pierwsze
// Algorytm nr 1
//------------------

#include <iostream>

using namespace std;

int main()
{
    setlocale(LC_ALL,"");

    cout << "Rozkład liczby na czynniki pierwsze" << endl
         << "-----------------------------------" << endl << endl;

    unsigned long long int L, p;

    cout << "L = "; cin >> L; cout << endl;

    cout << L << " : ";

    p = 2;
    while(L > 1)
        if(!(L % p))
        {
            cout << p << " ";
            L /= p;
        }
        else p++;

    cout << endl << endl;

    return 0;
}

Rozkład liczby na czynniki pierwsze
-----------------------------------

L = 288

288 : 2 2 2 2 2 3 3

Algorytm nr 1 jest bardzo prymitywny, ale oczywiście daje poprawne wyniki. Spróbujemy go teraz stopniowo poprawić.

Na początek wyeliminujmy z dzielników liczby parzyste - tylko jeden dzielnik może być liczbą parzystą: 2. Zmniejszy to o połowę liczbę dzieleń.

Algorytm nr 2: Rozkład na czynniki pierwsze

p ← 2
dopóki L > 1 wykonuj:
    jeśli L dzieli się przez p to
        pisz p
        L ← L : p
    inaczej
        jeśli p > 2, to p ← p + 2
        inaczej         p ← 3

// Rozkład na czynniki pierwsze
// Algorytm nr 2
//------------------

#include <iostream>

using namespace std;

int main()
{
    setlocale(LC_ALL,"");

    cout << "Rozkład liczby na czynniki pierwsze" << endl
         << "-----------------------------------" << endl << endl;

    unsigned long long int L, p;

    cout << "L = "; cin >> L; cout << endl;

    cout << L << " : ";

    p = 2; // Zaczynamy od dzielnika 2
    while(L > 1)
        if(!(L % p))
        {
            cout << p << " ";
            L /= p;
        }
        else if(p > 2) p += 2; // Następne będą nieparzyste
             else      p = 3;  // Pierwszy dzielnik nieparzysty

    cout << endl << endl;

    return 0;
}

Przy algorytmach wyznaczania liczb pierwszych powiedzieliśmy, iż liczby złożone posiadają dzielniki w przedziale od 2 do pierwiastka z badanej liczby. Pozwala nam to istotnie zredukować liczbę wykonywanych dzieleń.

Algorytm nr 3: Rozkład na czynniki pierwsze

p ← 2
g ← pierwiastek z L 
dopóki p ≤ g wykonuj:
    jeśli L = 1, to zakończ
    jeśli L dzieli się przez p to
        pisz p
        L ← L : p
    inaczej
        jeśli p > 2, to p ← p + 2
        inaczej         p ← 3
jeśli L > 1, to pisz L

// Rozkład na czynniki pierwsze
// Algorytm nr 3
//------------------

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    setlocale(LC_ALL,"");

    cout << "Rozkład liczby na czynniki pierwsze" << endl
         << "-----------------------------------" << endl << endl;

    unsigned long long int L, p, g;

    cout << "L = "; cin >> L; cout << endl;

    g = sqrt(L);

    cout << L << " : ";

    p = 2; // Zaczynamy od dzielnika 2
    while(p <= g)
    {
        if(L == 1) break; // Wychodzimy z pętli
        if(!(L % p))
        {
            cout << p << " ";
            L /= p;
        }
        else if(p > 2) p += 2; // Następne będą nieparzyste
             else      p = 3;  // Pierwszy dzielnik nieparzysty
    }

    if(L > 1) cout << L;       // Ostatni czynnik

    cout << endl << endl;

    return 0;
}

Instrukcja break powoduje natychmiastowe wyjście z pętli. Tutaj wykorzystujemy ją w przypadku, gdy wszystkie czynniki pierwsze zostały już znalezione, nie ma zatem sensu szukanie dalszych.

Porównaj ze sobą algorytmy wyszukiwania liczb pierwszych metodą podzielników i sita Eratostenesa oraz algorytmy rozkładu na czynniki pierwsze. Znajdź ich wspólne cechy i zapamiętaj je.

Przy rozwiązywaniu problemu zaczynamy od algorytmu prostego, który nazywamy naiwnym. Następnie staramy się wyeliminować z niego operacje puste, co powoduje przyspieszenie algorytmu. Tutaj często przydaje się wiedza matematyczna i logiczna. Takie działanie nazywamy optymalizacją algorytmu. Algorytmy naiwne zwykle działają wolno, algorytmy zoptymalizowane zwykle działają szybciej, chociaż są bardziej skomplikowane – ta zasada często obowiązuje w informatyce dla wielu algorytmów.

Zadanie:

Zapisz algorytm nr 3 w postaci listy kroków i schematu blokowego.

Więcej na temat rozkładu liczby naturalnej na czynniki pierwsze znajdziesz w osobnym artykule.

Do zapamiętania:

• Algorytm nr 3 rozkładu liczby na czynniki pierwsze
• Instrukcja break.