# Divizibilitate, numere prime și algoritmul lui Euclid

> Pagina: https://bacalaurescu.ro/informatica/lectii/algoritmi-clasici-bac/divizibilitate-si-euclid
> Markdown: https://bacalaurescu.ro/informatica/lectii/algoritmi-clasici-bac/divizibilitate-si-euclid.md
> Sursa: Bacalaurescu (bacalaurescu.ro), conținut gratuit pentru BAC 2027.

Materia: [Informatică](https://bacalaurescu.ro/informatica)

Capitolul: [Algoritmi clasici de BAC](https://bacalaurescu.ro/informatica/lectii/algoritmi-clasici-bac)
Actualizat: 2026-09-22

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

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

> [!RETINE]
> 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

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.