Największy wspólny dzielnik

Największy wspólny dzielnik kilku liczb to największa liczba naturalna dzieląca wszystkie z tych liczb. Obliczanie NWD dla małych liczb można wykonać ręcznie w pamięci, jednak przy większych liczbach dobrze posłużyć się pewnymi algorytmami (np. algorytmem Euklidesa).

Największy wspólny dzielnik

W celu obliczenia największego wspólnego dzielnika należy przeprowadzić następujące kroki:

1. Rozłożyć liczby na iloczyn czynników pierwszych (instrukcja jak rozkładać na czynniki pierwsze)
2. Wymnożyć wspólne czynniki pierwsze, które powtarzają się zarówno dla jednej i drugiej liczby.

Przykładowo, obliczmy NWD dla liczb 56 i 100:

\[56=2*2*2*7\] \[100=2*2*5*5\]

Jedyne wspólne czynniki pierwsze to 2 i 2. W takim razie:

\[NWD(56,100)=2*2=4\]

Program w C++ (iteracyjny)

Przykładowy program, pozwalający obliczyć największy wspólny dzielnik dwóch liczb, za pomocą algorytmu Euklidesa.

#include <iostream>
#include <cstdlib>

using namespace std;

int main()
{
    int a, b;
    cout << "Podaj pierwsza liczbe: ";
    cin >> a;
    cout << "Podaj druga liczbe: ";
    cin >> b;

    do
    {
        if(a > b) {
            a = a - b;
        } else {
            b = b - a;
        }
    }
    while(a != b);

    cout << "Najwiekszy wspolny dzielnik: " << a << endl;

    system("PAUSE");

    return 0;
}

Rozkład liczby na czynniki pierwsze

Znajdowanie najmniejszego i największego elementu

Sprawdzanie wielkości litery