Matura z informatyki - rozwiązania zadań  

Algorytmy

Rozkładanie liczby na czynniki pierwsze

Każda liczba naturalna n może zostać jednoznacznie zapisana jako iloczyn liczb pierwszych. Jednoznacznie oznacza, że istnieje tylko jeden zbiór liczb pierwszych, których iloczyn daje w wyniku podaną liczbę. Przy czym możemy tutaj wyróżnić dwa przypadki:

  • liczby złożone - posiadają więcej niż jeden czynnik pierwszy
  • liczby pierwsze - posiadają tylko jeden czynnik pierwszy (samą siebie)

Rozkład na czynniki pierwsze polega na znalezieniu dla danej liczby naturalnej n, n > 1, wszystkich liczb pierwszych, których iloczyn daje n.

Daną liczbę n będziemy próbowali dzielić przez kolejne liczby i od 2 do pierwiastka z n. Jeśli dzielenie przez i jest możliwe (dostajemy resztę z dzielenia równą 0), to zapamiętamy czynnik i, podzielimy przez niego n i operację powtórzymy. Gdy dzielenie przestanie być już możliwe, sprawdzimy, czy n nie zredukowało się nam do 1. W takim przypadku znaleźliśmy już wszystkie czynniki dzielące n i algorytm przerwiemy. Jeśli n będzie wciąż większe od 1, to nie znaleźliśmy jeszcze wszystkich czynników. Dzielnik i zwiększamy o 1 i znów próbujemy dzielić. Gdy i przekroczy wartość pierwiastka z początkowego n, to ostatni czynnik jest większy od tego pierwiastka i znajduje się w bieżącej wartości n - wystarczy zatem zapamiętać ten ostatni czynnik i zakończyć algorytm.

Przykład:

Przeanalizujmy rozkład liczby n = 36:

Pierwiastek z 36 wynosi 6, zatem dzielniki będą kolejno przyjmowały wartości od 2 do 6:

36 : 2 = 18 - dzieli się, czynnik 2

18 : 2 = 9 - dzieli się, czynniki 2 2

9 : 2 = - nie dzieli się, bierzemy kolejny dzielnik 3

9 : 3 = 3 - dzieli się, czynniki 2 2 3

3 : 3 = 1 - dzieli się, czynniki 2 2 3 3 - koniec, gdyż n zredukowało się do 1

36 = 2 × 2 × 3 × 3

#include <iostream>
#include <cmath>

using namespace std;

void czynnikiPierwsze(unsigned n)
{
    unsigned p, i;

    //deklarujemy zmienna p i przypisujemy
    //do niej pierwiastek z liczby n
    p = sqrt(n);

    for (i = 2; i <= p; i++) {
        while (n % i == 0) {
            cout << i << " ";
            n /= i;
        }

        if (n == 1) {
            cout << endl;
            return;
        }
    }

    cout << n << endl;
}

int main()
{
    unsigned n;

    cout << "Program rozklada liczbe naturalna n na czynniki pierwsze." << endl;

    cout << "Podaj liczbe naturalna n wieksza od 1" << endl;

    cin >> n;

    cout << "Czynniki pierwsze liczby " << n << " to:" << endl;

    czynnikiPierwsze(n);

    cin.get();
    return 0;
}
© 2017 MaturaInformatyka.pl || Kontakt: admin(malpa)maturainformatyka.pl

Search