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:

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  

 

 

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

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

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