Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

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

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

Matura - programowanie w C++

Rozkład na czynniki pierwsze

SPIS TREŚCI

Liczby złożone

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:


Na początek:  podrozdziału   strony 

Rozkład na czynniki pierwsze

Pierwszy sposób rozkładu na czynniki pierwsze polega na wykonywaniu próbnych dzieleń całkowitych liczby L przez kolejne liczby p od 2 w górę. Jeśli L dzieli się przez p, to p jest czynnikiem, p wypisujemy, a za nowe L przyjmujemy wynik dzielenia i powtarzamy dzielenie. Jeśli L nie dzieli się przez p, to p zwiększamy o 1 i powtarzamy całą procedurę, aż L stanie się równe 1.

Przykład:

Rozłożyć na czynniki pierwsze liczbę L = 288.

Zaczynamy od p = 2:

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

Dane wejściowe: L - rozkładana na czynniki pierwsze liczba naturalna, L > 1

Dane wyjściowe: rozkład na czynniki pierwsze liczby L

Pseudokod:   

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

Program C++:

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

Dane wejściowe: L - rozkładana na czynniki pierwsze liczba naturalna, L > 1

Dane wyjściowe: rozkład na czynniki pierwsze liczby L

Pseudokod:   

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

Program C++:

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

Dane wejściowe: L - rozkładana na czynniki pierwsze liczba naturalna, L > 1

Dane wyjściowe: rozkład na czynniki pierwsze liczby L

Pseudokod:   

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

Program C++:

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


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