Divizibilitate: algoritmi pentru cmmdc, cmmmc, numere prime

Divizibilitatea este o proprietate fundamentală a numerelor naturale, care studiază când un număr se împarte exact la altul. Spunem că a este divizibil cu b (și notăm b|a) dacă există un număr natural c astfel încât a = b * c. În această lecție vom învăța trei concepte importante: cel mai mare divizor comun (cmmdc), cel mai mic multiplu comun (cmmmc) și numerele prime.

Cel mai mare divizor comun a două numere a și b este cel mai mare număr natural care le divide pe amândouă. Algoritmul lui Euclid este o metodă eficientă de a-l calcula: cât timp b != 0, se face a = b, b = a % b (restul împărțirii lui a la b). La final, a este cmmdc.

De exemplu, pentru 24 și 36: 24 % 36 = 24, apoi 36 % 24 = 12, apoi 24 % 12 = 0, deci cmmdc = 12. Cel mai mic multiplu comun este cel mai mic număr natural care este multiplu al ambelor numere. O formulă simplă: cmmmc(a,b) = a * b / cmmdc(a,b).

De exemplu, pentru 4 și 6: cmmdc=2, deci cmmmc = 4*6/2=12. Numerele prime sunt numere naturale mai mari decât 1 care au exact doi divizori: pe 1 și pe ele însele. Un algoritm simplu pentru a verifica dacă un număr n este prim este să testăm divizorii de la 2 până la radicalul lui n (inclusiv).

Dacă n are vreun divizor în acest interval, atunci nu este prim. De exemplu, 7 este prim (divizori: 1 și 7), iar 9 nu este prim (divizibil și cu 3). Pentru a genera numere prime până la un n, putem folosi Ciurul lui Eratostene: se creează un vector boolean cu n+1 elemente, inițial toate true (cu excepția lui 0 și 1).

Apoi, pentru fiecare i de la 2 la radicalul lui n, dacă i este prim, se marchează ca false toți multiplii lui i începând cu i*i. La final, toate elementele true sunt numere prime. În informatică, acești algoritmi se implementează eficient pentru probleme de concurs sau aplicații practice precum criptografia.

Exemple

• Exemplul 1: Calculați cmmdc(60, 48) folosind algoritmul lui Euclid. Pasul 1: 60 mod 48 = 12, a=48, b=12. Pasul 2: 48 mod 12 = 0, a=12, b=0. Rezultat: cmmdc = 12.
• Exemplul 2: Calculați cmmmc(15, 25). Aflăm cmmdc: 15 mod 25 = 15, 25 mod 15 = 10, 15 mod 10 = 5, 10 mod 5 = 0, deci cmmdc=5. Atunci cmmmc = 15*25/5 = 75. Verificare: 75 este multiplu de 15 (15*5) și de 25 (25*3).
• Exemplul 3: Verificați dacă 29 este număr prim. Radicalul lui 29 este aproximativ 5.38, deci testăm divizorii 2,3,5. 29%2=1, 29%3=2, 29%5=4, niciunul nu dă rest 0, deci 29 este prim.

Concepte cheie: Cel mai mare divizor comun (cmmdc) prin algoritmul lui Euclid, Cel mai mic multiplu comun (cmmmc) folosind formula cmmmc = a*b / cmmdc, Verificarea numerelor prime prin testarea divizorilor până la radicalul numărului, Generarea numerelor prime prin Ciurul lui Eratostene, Proprietatea numerelor prime între ele și aplicațiile lor