Divizibilitate, numere prime și algoritmul lui Euclid

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

Greșeli frecvente

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

#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;
}