Divizibilitatea

De-a lungul parcursului vostru în domeniul algoritmicii, precum și de multe ori în diferite olimpiade și concursuri de informatică, va trebui să rezolvați multe probleme care se bazează pe un fundament matematic, studiul teoriei din spatele divizibilității numerelor naturale precum și a algoritmilor de aflare a numerelor prime, numărului de divizori, lucrului eficient cu numerele prime devenind toate foarte importante pentru asimilarea în cel mai bun mod posibil a acestui capitol. Totuși, acest document reprezintă doar un punct de plecare în ceea ce privește aplicațiile teoriei numerelor în algoritmică, alte concepte fiind discutate în documentele ulterioare. Aceste noțiuni se vor găsi foarte des în problemele de informatică pentru clasele de gimnaziu și clasa a IX-a.

Noțiuni introductive

Definiție

Un număr $x$ este numit divizor al altui număr $y$ , dacă $y$ se poate scrie ca produsul dintre $x$ și un alt număr întreg $t$ .

Observație

Orice număr $n$ se împarte la 1 și la el însuși.

Divizor comun

Definim un divizor comun al unei perechi de numere $(a, b)$ ca fiind un număr $c$ care este un divizor atât al lui $a$ , cât și al lui $b$ .

CMMDC și CMMMC

Definim cel mai mare divizor comun (cmmdc) al unei perechi de numere $(a, b)$ ca fiind cel mai mare număr care este un divizor atât al lui $a$ , cât și al lui $b$ . Vom nota $x = (a, b)$ . Definim cel mai mic multiplu comun (cmmmc) al unei perechi de numere $\[a, b]$ ca fiind cel mai mic număr care este un multiplu atât al lui $a$ , cât și al lui $b$ . Vom nota $x = \[a, b]$ .

Observație

$a \cdot b = (a, b) \cdot \[a, b]$ . Drept concluzie:

(a, b) = \frac{a \cdot b}{[a, b]}

Pentru aflarea celui mai mare divizor comun a două numere, există doi algoritmi principali. Primul dintre ei se bazează pe scăderi repetate, la fiecare pas scăzându-se din numărul mai mare, numărul mai mic până când cele două valori devin egale. Deși pentru multe perechi de numere acest algoritm este destul de eficient, atunci când diferența dintre numere este foarte mare, algoritmul va rula în timp cvasi-liniar (de exemplu, pentru numerele 3 și $10^9$ , un calculator are nevoie de câteva secunde să afle cmmdc-ul folosind acest algoritm).

De aceea vom folosi algoritmul lui Euclid prin împărțiri repetate pentru a ajunge la răspuns. Acest algoritm pleacă de la ideea că o slăbiciune majoră a algoritmului prin scăderi este dată de situația când raportul dintre numărul mai mare și cel mai mic este foarte mare, când practic efectuăm aceeași operație de foarte multe ori. De aceea, în loc de scăderi, la fiecare pas vom afla restul împărțirii numărului mai mare la cel mai mic, înlocuind posibilele operații de scădere cu o singură împărțire, algoritmul devenind mult mai eficient.

Exemplu

De exemplu, să analizăm numerele 40 și 18.

$a = 40$ , $b = 18$ . $a \% b = 4$ , noile valori fiind $a = 18$ , $b = 4$ ;
$a = 18$ , $b = 4$ . $a \% b = 2$ , noile valori fiind $a = 4$ , $b = 2$ ;
$a = 4$ , $b = 2$ . $a \% b = 0$ , noile valori fiind $a = 2$ , $b = 0$ ;
$a = 2$ , $b = 0$ . Deoarece $b = 0$ , continuarea algoritmului ne-ar duce la împărțiri la 0, operație ce nu este validă.

Mai jos puteți găsi implementarea în C++ a cmmdc-ului și a cmmmc-ului, program ce află cmmdc și cmmmc pentru $t$ perechi de numere. Complexitatea algoritmului este $\mathcal{O}(\log n)$ pentru fiecare test.

Pentru calcularea CMMMC-ului, trebuie avut grijă să împărțim mai întâi la $cmmdc(a, b)$ și apoi să înmulțim cu $b$ , pentru a evita un potențial overflow.

--8 < --"usor/divizibilitate/cmmmc.cpp"

Sfat

C++17 oferă std::gcd() și std::lcm() în <numeric>, deci nu este nevoie să reimplementați algoritmul dacă aveți acces la un asemenea compilator.

Lucrul cu divizorii unui număr

Numere prime și compuse

Un număr $n \geq 2$ este număr prim dacă și numai dacă are doar 2 divizori: $1$ și $n$ , în caz contrar fiind număr compus.

0 și 1 nu sunt nici numere prime, nici numere compuse.
2 este singurul număr prim par, celelalte numere prime fiind impare.

Descompunerea în factori primi se bazează pe Teorema fundamentală a aritmeticii, dată mai jos:

Teorema fundamentală a aritmeticii

Orice număr natural $n > 1$ se poate scrie în mod unic sub forma $n = \prod_{i = 1}^k p_i^{e_i}$ unde $p_1 < p_2 < \dots < p_k$ sunt numere prime, iar $e_i \in \mathbb{N}^\ast~\forall 1 \leq i \leq k$ .

Observație

Se poate observa că numărul maxim de numere prime la care se împarte un număr $n$ este foarte mic. De exemplu, pentru $n \leq 10^{9}$ , sunt cel mult 9 numere prime în reprezentarea ca produs de factori primi.

Pentru a afla divizorii unui număr natural $n$ , cel mai simplu (dar și ineficient) algoritm constă în a verifica pe rând fiecare număr 1 la $n$ și să verificăm dacă $n$ se împarte exact la acel număr. Pentru a optimiza acest algoritm, va trebui să folosim o altă observație importantă.

Observație

Dacă $n$ se împarte exact la $x$ , se va împărți exact și la $\frac{n}{x}$ . Așadar, $x^2 \leq n$ sau $x \leq \sqrt{n}$ . Asta ne duce la ideea să verificăm doar divizorii până la $\sqrt{n}$ , observație ce se va dovedi fundamentală în calculele și algoritmii pe care îî vom scrie pentru toate aceste probleme.

Astfel, vom putea afla orice informație legată de divizorii unui număr în $\mathcal{O}(\sqrt{n})$ , fie că e vorba de numărul de divizori, divizorii primi, descompunerea în factori primi și așa mai departe.

Totuși, putem verifica cu ușurință pentru un număr $n$ dacă $d$ este divizor al acestuia, folosind o simplă condiție aritmetică

if (n % d == 0) {
    cout << d << " este divizor al lui " << n << '\n';
}

Problema divizibilitate

View Problem

Kilonova

Could not fetch problem details

Deschide

Fiecare tip de întrebare a fost implementat folosind o funcție separată pentru a arăta diferențele ce pot apărea de la un tip de întrebare la alta.

--8 < --"usor/divizibilitate/divizibilitate.cpp"

Divizibilitatea

Noțiuni introductive

Lucrul cu divizorii unui număr

Problema divizibilitate

View Problem

Probleme suplimentare

Lectură suplimentară

On this page