Capitolul 18 · Lecția 18.1 din 4

Divizibilitate, numere prime și algoritmul lui Euclid

Testul de primalitate, divizorii, cmmdc prin scăderi și prin împărțiri, cmmmc.

Capitolul 18: Algoritmi clasici de BAC

Pe această pagină5 secțiuni

Testul de primalitate

Un număr $n \geq 2$ e prim dacă nu are alți divizori în afară de 1 și el însuși.

Nu e nevoie să testezi până la $n$ . E suficient până la $\sqrt{n}$ , pentru că divizorii vin în perechi: dacă $d$ divide $n$ , atunci și $n/d$ divide $n$ , iar unul dintre ei e mereu $\leq \sqrt{n}$ .

Complexitate: de la $O(n)$ la $O(\sqrt{n})$ .

Cazuri speciale: 0 și 1 nu sunt prime. 2 e singurul număr prim par.

Divizorii unui număr

Aceeași observație: parcurgi $d$ de la 1 la $\sqrt{n}$ și pentru fiecare divizor găsit adaugi și perechea lui.

Algoritmul lui Euclid

Calculează cel mai mare divizor comun (cmmdc).

Varianta cu scăderi: cât timp $a \neq b$ , scade din cel mare pe cel mic. Când devin egale, aia e valoarea.

Varianta cu împărțiri (mult mai rapidă): $\text{cmmdc}(a, b) = \text{cmmdc}(b, a \bmod b), \quad \text{cmmdc}(a, 0) = a$

Repeți până restul devine 0. Ultimul rest nenul e răspunsul.

Exemplu: cmmdc(48, 18):

48 mod 18 = 12 → (18, 12)
18 mod 12 = 6 → (12, 6)
12 mod 6 = 0 → răspuns 6

Cel mai mic multiplu comun

$\text{cmmmc}(a, b) = \frac{a \cdot b}{\text{cmmdc}(a, b)}$

Atenție la depășire: la numere mari, $a \cdot b$ poate depăși tipul. Se împarte întâi: $(a / \text{cmmdc}) \cdot b$ .

Reține

Testul până la $\sqrt{n}$ și formula cmmmc = a·b/cmmdc sunt două dintre cele mai frecvente cerințe de la Subiectul II și III. Merită știute pe de rost.

Greșeli frecvente

Se consideră 1 număr prim. Nu este.
Se testează divizibilitatea până la $n/2$ în loc de $\sqrt{n}$ . Corect, dar mai lent; la limite mari pică pe timp.
La cmmmc se înmulțește întâi și se depășește tipul. Împarte întâi.

Exemplul, în 4 limbaje

Alege limbajul în care dai examenul. Poți edita codul și îl poți rula direct aici. Programa oficiala de BAC (proba E.d) cere Pascal sau C/C++, la alegere. Python apare in manualele noi si e pus aici pentru inteles, nu ca limbaj de examen.

#include <iostream>
using namespace std;

int cmmdc(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

bool prim(int n) {
    if (n < 2) return false;
    for (int d = 2; d * d <= n; d++)
        if (n % d == 0) return false;
    return true;
}

int main() {
    int a, b;
    cin >> a >> b;
    int d = cmmdc(a, b);
    cout << "cmmdc=" << d << " cmmmc=" << (a / d) * b << " ";
    cout << a << (prim(a) ? " prim" : " neprim");
    return 0;
}