Clasa a IX-a · Divizibilitate și numere primeRead in English

Cmmdc prin scăderi repetate în C++

În engleză: GCD by repeated subtraction

O(n)C++1736 de linii1 exemplu

Ideea

Scădem numărul mai mic din cel mai mare până când devin egale; valoarea comună este cmmdc-ul. Merge doar pentru a, b > 0 (cu un 0 bucla nu s-ar opri). Este mai lent decât varianta cu împărțiri: pentru 1000000 și 1 face aproape un milion de pași.

Descrierea în engleză

We subtract the smaller number from the larger one until they become equal; the common value is the GCD. It only works for a, b > 0 (with a 0 the loop would never stop). It is slower than the division version: for 1000000 and 1 it takes almost a million steps.

Complexitate
O(max(a, b)) în cazul cel mai rău
Clasa
Clasa a IX-a (Grade 9)

Exemple

Exemplul 1

Intrare

48 18

Ieșire așteptată

6

Codul C++

Codul complet, cu comentarii în română. Îl poți modifica liber și îl poți reseta oricând.

cmmdc-prin-scaderi.cpp
/*
 * Titlu: Cmmdc prin scăderi repetate
 * Clasa: 9
 * Capitol: Divizibilitate și numere prime
 * Descriere: Scădem numărul mai mic din cel mai mare până când devin egale;
 *            valoarea comună este cmmdc-ul. Merge doar pentru a, b > 0 (cu un 0
 *            bucla nu s-ar opri). Este mai lent decât varianta cu împărțiri:
 *            pentru 1000000 și 1 face aproape un milion de pași.
 * Complexitate: O(max(a, b)) în cazul cel mai rău
 *
 * Exemplu
 * Intrare: 48 18
 * Ieșire: 6
 */
#include <iostream>
using namespace std;

int main()
{
    long long a, b;
    cin >> a >> b;
    while (a != b)
    {
        if (a > b)
        {
            a = a - b;
        }
        else
        {
            b = b - a;
        }
    }
    cout << a << '\n';
    return 0;
}

Rulează pe un g++ adevărat (C++17, -O2) prin Compiler Explorer. Programele trebuie să se termine repede: există o limită de timp.