obrazek

Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych.
Autor artykułu: mgr Jerzy Wałaszek, wersja1.0

obrazek

Pomoce:

Instalacja Code Blocks i tworzenie projektu aplikacji konsoli.
System uzupełnień do podstawy - U2
Wprowadzenie do języka C++, strumienie i zmienne
Komputer podejmuje decyzje
Pętle warunkowe

Pętla iteracyjna
Wprowadzenie do algorytmów, algorytm Euklidesa
Generacja liczb pierwszych przez sprawdzanie podzielności
Tablice
Sito Eratostenesa

Rozkład na czynniki pierwsze

Zbiór liczb naturalnych większych od 1 dzieli się na dwa rodzaje liczb:

Liczby pierwsze, które nie są iloczynami żadnych mniejszych liczb z tego zbioru: 2, 3, 5, 7, 11, 13, 17, 19...
Liczby złożone, które są iloczynami liczb mniejszych: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18...

Rozkład na czynniki pierwsze (ang. prime factorization) polega na znalezieniu dla danej liczby naturalnej n, n > 1, wszystkich liczb pierwszych, których iloczyn daje n. Zadanie to można rozwiązać na kilka różnych sposobów, jednakże nie istnieje żaden prosty wzór, który by pozwolił łatwo wyznaczać wszystkie czynniki pierwsze rozkładu - należy ich szukać. My podejdziemy do problemu w sposób następujący:

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:

Znajdziemy 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

Znajdziemy rozkład liczby n = 66:

Pierwiastek z 66 wynosi 8,12..., dzielniki od 2 do 8.

66 : 2 =	33	- dzieli się, czynnik 2
33 : 2 =		- nie dzieli się, bierzemy kolejny dzielnik 3
33 : 3 =	11	- dzieli się, czynniki 2 3
11 : 3 =		- nie dzieli się, bierzemy kolejny dzielnik 4
11 : 4 =		- nie dzieli się, bierzemy kolejny dzielnik 5
11 : 5 =		- nie dzieli się, bierzemy kolejny dzielnik 6
11 : 6 =		- nie dzieli się, bierzemy kolejny dzielnik 7
11 : 7 =		- nie dzieli się, bierzemy kolejny dzielnik 8
11 : 8 =		- nie dzieli się, koniec, ponieważ wykorzystaliśmy wszystkie dzielniki, czynniki 2 3 11

66 = 2 × 3 × 11

Algorytm rozkładu na czynniki pierwsze

Wejście:

n - liczba naturalna, której rozkładu poszukujemy, n > 1.
Wyjście:

Czynniki pierwsze liczby n.

Dane pomocnicze:

g - wartość pierwiastka z n
i - dzielniki

Krok 1:	g ← √n	; wyznaczamy górną granicę podzielników
Krok 2:	i ← 2	; ustalamy pierwszy dzielnik
Krok 3:	Jeśli i > g, to idź do kroku 11	; sprawdzamy, czy przetworzono wszystkie dzielniki
Krok 4:	Jeśli n nie dzieli się przez i, to idź do kroku 8	; sprawdzamy, czy i jest czynnikiem n
Krok 5:	Pisz i	; jest, wyprowadzamy czynnik i
Krok 6:	n ← n / i	; usuwamy czynnik i z n
Krok 7:	Idź do kroku 4	; powtarzamy sprawdzenie podzielności n przez i
Krok 8:	Jeśli n = 1, to zakończ	; sprawdzamy, czy znaleziono wszystkie czynniki pierwsze
Krok 9:	i ← i + 1	; nie, bierzemy następny dzielnik
Krok 10:	Idź do kroku 3	; i powtarzamy test
Krok 11:	Pisz n	; w n pozostał czynnik większy od pierwiastka z n
Krok 12:	Zakończ

obrazek

// Rozkład na czynniki pierwsze
// (C)2010 I LO w Tarnowie
//------------------------

#include <iostream>
#include <cmath>

using namespace std;

// Funkcja wypisuje wszystkie czynniki pierwsze liczby n
//------------------------------------------------------

void czynniki(unsigned n)
{
    unsigned g,i;

    g = sqrt(n);

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

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

    cout << n << endl;
}

int main()
{
    unsigned n;

    cin >> n;

    czynniki(n);

    return 0;
}

Wykorzystaj powyższy program do znajdowania rozkładu na czynniki pierwsze kolejnych liczb naturalnych od 2 do zadanej wartości n.

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe