SISergiu Ilincameditații informatică
Meniu

clasa a IX-a · Algoritmi elementari · lecția 10

Divizibilitate: divizori, numere prime, cmmdc și cmmmc

60 mintoate profilurile

Înainte de lecția asta: IX.8 Algoritmi elementari: sume, produse, numărări, maxim și minim

Ce vei ști după lecție

  • Parcurgi divizorii unui număr eficient, până la √n.
  • Verifici dacă un număr este prim în O(√n).
  • Calculezi cmmdc cu algoritmul lui Euclid (prin împărțiri și prin scăderi) și cmmmc.
  • Recunoști numerele perfecte, prime între ele și alte proprietăți uzuale.

Lecția are și o fișă de lucru, de rezolvat după ce o citești. Mergi la fișă ↓

Fișiere PDF și de lucru

1. Divizori: varianta simplă și varianta eficientă

d este divizor al lui n dacă n % d == 0.

Varianta simplă (n pași): încerci toate numerele de la 1 la n.

for (int d = 1; d <= n; d++)
    if (n % d == 0) cout << d << ' ';

Varianta eficientă (√n pași): divizorii vin în perechi (d, n / d). Dacă d ≤ √n, perechea lui e ≥ √n. Deci e de ajuns să căutăm până la √n, adică până când d · d > n.

Perechile de divizori

#include <iostream>
using namespace std;

int main()
{
    int n, nrDiv = 0, sumaDiv = 0;
    cin >> n;
    for (int d = 1; d * d <= n; d++)
        if (n % d == 0)
        {
            nrDiv++;  sumaDiv += d;
            if (d != n / d) { nrDiv++;  sumaDiv += n / d; }   // perechea, dacă e diferită
        }
    cout << nrDiv << " " << sumaDiv;
    return 0;
}

Urmărire pentru n = 12:

d d * d <= 12? 12 % d == 0? perechea n/d nrDiv sumaDiv
1 da da 12 2 13
2 da da 6 4 21
3 da da 4 6 28
4 nu (16 > 12) → stop 6 28

De ce așa?

De ce se poate opri la √n? Dacă d · e = n și ambii ar fi mai mari decât √n, produsul ar depăși n. Deci cel puțin unul dintre ei e ≤ √n: găsind pe cel mic, îl obții pe cel mare ca n / d. Pentru n = 10⁹ treci de la un miliard de pași la circa 31 600.

Atenție — greșeli frecvente

Pentru pătratele perfecte (de exemplu 36 = 6 · 6), perechea lui 6 este tot 6: nu o număra de două ori. De aici condiția d != n / d.

Sfat

Un număr are un număr impar de divizori dacă și numai dacă este pătrat perfect (unicul divizor fără pereche este √n). Apare des la grile.

2. Numere prime

Un număr este prim dacă are exact doi divizori: 1 și el însuși. 0 și 1 nu sunt prime; 2 este singurul număr prim par.

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    bool prim = (n >= 2);
    for (int d = 2; d * d <= n && prim; d++)
        if (n % d == 0)
            prim = false;
    cout << (prim ? "DA" : "NU");
    return 0;
}
n d încercați rezultat
97 2, 3, 4, 5, 6, 7, 8, 9 (10·10 = 100 > 97) niciun divizor → prim
91 2, 3, 4, 5, 6, 7 → 91 % 7 == 0 nu e prim (7 · 13)

Pentru n ≈ 10⁹, verificarea face cel mult ~31 623 pași în loc de un miliard.

De ce așa?

De ce variabila prim și nu break? Ambele merg. Cu prim în condiția buclei (&& prim) ieșirea e vizibilă chiar în antet, iar la BAC se cere des „fără instrucțiuni break/continue”. De reținut: pornim cu „prim = adevărat” și căutăm un contra-exemplu; un singur divizor îl dărâmă.

La BAC

La Subiectul III (eficiență) se punctează diferit o verificare de primalitate până la n, până la n/2 sau până la √n. Folosește mereu varianta d * d <= n.

3. Cel mai mare divizor comun: algoritmul lui Euclid

Ideea: orice număr care divide pe a și pe b divide și restul a % b. Deci cmmdc(a, b) = cmmdc(b, a % b), iar problema devine mai mică la fiecare pas, până când restul e 0.

Euclid pentru 48 și 18

Prin împărțiri (rapid):

#include <iostream>
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    while (b != 0)
    {
        int r = a % b;
        a = b;
        b = r;
    }
    cout << a;                // cmmdc
    return 0;
}
pas a b r = a % b
1 48 18 12
2 18 12 6
3 12 6 0
4 6 0 (b = 0: stop) → cmmdc = 6

De ce așa?

De ce rămâne a și nu b la final? Când b devine 0, ultimul rest nenul s-a mutat în a prin a = b. Din același motiv cmmdc(a, 0) = a: orice număr se divide cu el însuși, iar 0 se divide cu orice.

Prin scăderi repetate (apare la Bac în pseudocod, trebuie să-l recunoști):

cât timp a ≠ b execută
   dacă a > b atunci a ← a - b
   altfel b ← b - a
   

scrie a

Capcană

Varianta cu scăderi intră în buclă infinită dacă unul dintre numere este 0. Varianta cu împărțiri funcționează și atunci: cmmdc(a, 0) = a.

Cel mai mic multiplu comun

cmmmc(a, b) = a · b / cmmdc(a, b). Ca să nu depășești, împarte întâi:

long long cmmmc = 1LL * a / g * b;   // g = cmmdc(a, b), calculat pe copii ale lui a și b

De ce așa?

De ce a / g * b și nu a * b / g? Rezultatul e același, dar a * b poate depăși int înainte să împarți. a / g este întreg (g îl divide pe a), apoi înmulțești cu b. Ordinea operațiilor contează la numere mari.

Proprietăți utile

  • a și b sunt prime între ele dacă cmmdc(a, b) = 1.
  • Fracția a/b se simplifică împărțind ambii termeni la cmmdc(a, b).
  • cmmdc pentru n numere: g = cmmdc(g, x) pentru fiecare număr nou.

4. Alte numere „cu nume”

Denumire Definiție Exemple
perfect egal cu suma divizorilor săi mai mici decât el 6, 28, 496
prime între ele cmmdc = 1 8 și 15
pătrat perfect r * r == n, cu r = (int)sqrt(n) 49, 144
prime gemene prime cu diferența 2 11 și 13
numere prietene fiecare = suma divizorilor proprii ai celuilalt 220 și 284

Pentru pătrat perfect, verifică vecinii lui r ca să eviți erorile de rotunjire ale lui sqrt:

int r = sqrt(n);
while (r * r > n) r--;
while ((r + 1) * (r + 1) <= n) r++;
bool patrat = (r * r == n);

5. Greșeli frecvente

Greșeala Efect Corect
d <= n în loc de d * d <= n prea lent la n mare d * d <= n
1 declarat prim răspuns greșit n >= 2
pătrat perfect numărat de două ori un divizor în plus d != n / d
a * b / g la numere mari depășire a / g * b
Euclid prin scăderi cu 0 buclă infinită împărțiri

6. La BAC

La BAC

Subiectul I conține adesea o grilă cu divizori (câți, care e cel mai mare) și una cu pseudocod pe cmmdc (ce afișează pentru a, b date). Subiectul III cere un program cu verificare de primalitate sau numărarea divizorilor la valori mari (n până la 2·10⁹): numai varianta d * d <= n ia punctajul complet.

7. Exersează pe hârtie

Răspunsurile sunt la final: încearcă întâi singur.

1. Ce afișează pentru a = 12, b = 30? Ce calculează?

citește a, b
cât timp a ≠ b execută
   dacă a > b atunci a ← a - b
   altfel b ← b - a
   

scrie a

2. Câte numere din intervalul [1, 100] au exact 3 divizori? (Indiciu: pătrate de numere prime.)

3. Câți divizori are 36? Este un număr impar? De ce?

4. Calculează cmmdc(84, 36) și cmmmc(84, 36) cu Euclid.

5. De câte ori se execută corpul buclei for (d = 2; d * d <= 97; d++) pentru n = 97? Este 97 prim?

6. Ce afișează Euclid prin împărțiri pentru a = 18, b = 0? Dar varianta prin scăderi?

7. Simplifică fracția 45/60 folosind cmmdc.

8. Care dintre numerele 12 și 28 este perfect?

9. Scrie un program eficient care afișează câți divizori are n ≤ 2 000 000 000 (indiciu: ce tip folosești pentru d * d?).

8. Mai departe (pentru cine vrea mai mult)

Ciurul lui Eratostene. Pentru toate numerele prime până la n nu verifici fiecare număr separat. Marchezi multiplii fiecărui prim:

Ciurul lui Eratostene

vector<bool> prim(n + 1, true);
prim[0] = prim[1] = false;
for (int i = 2; i * i <= n; i++)
    if (prim[i])
        for (int j = i * i; j <= n; j += i)
            prim[j] = false;

Lucrează în aproximativ n · log log n pași: numerele prime până la 10 milioane în sub o secundă. Îl vei folosi în clasa a X-a la vectori.

Criptografie. Securitatea cumpărăturilor online (RSA) se bazează pe un fapt simplu: înmulțirea a două numere prime uriașe e ușoară, dar descompunerea produsului în factori e imposibilă în timp rezonabil. Tot ce ai învățat în lecție (primalitate, cmmdc, Euclid extins) este fundația matematică a ei.

Euclid are 2300 de ani. Algoritmul apare în „Elementele” lui Euclid (aproximativ 300 î.Hr.) și este considerat cel mai vechi algoritm încă în folosință. Pentru n numere se aplică repetat: g = cmmdc(g, x).

Teorema lui Euclid: există o infinitate de numere prime. Demonstrația are patru rânduri: presupune că ai o listă finită de prime, înmulțește-le și adaugă 1. Noul număr nu se divide cu niciunul din listă, deci are un factor prim care nu era în listă: lista nu putea fi completă.

Rezumat

  • Divizori până la √n, în perechi (d, n/d); atenție la pătratele perfecte.
  • Prim: n ≥ 2 și niciun divizor în [2, √n].
  • Euclid: r = a % b; a = b; b = r; până când b == 0.
  • cmmmc = a / cmmdc * b.
  • Numărul de divizori este impar exact pentru pătrate perfecte.

Fișa de lucru

Ai citit lecția? Printează fișa sau deschide-o pe ecran și rezolvă exercițiile în ordine.

Fișă de lucru · 6 pagini · 100 min

Divizibilitate, numere prime, cmmdc, factori primi

  • Parcurgi divizorii până la √n și verifici primalitatea fără greșelile clasice (1, pătratele perfecte, depășirea).
  • Folosești Euclid pentru cmmdc, cmmmc, fracții și probleme „cu grupe egale” sau „cu întâlniri”.
  • Descompui în factori primi și citești din descompunere: numărul divizorilor, zerourile de la final, cmmdc.

Fișa acoperă și: IX.11

Te-ai blocat la un exercițiu?

Probleme de lucru

Începe cu acestea, în ordine. Problemele se deschid pe pbinfo.ro, unde trimiți soluția și primești punctajul.

  • verifprim#45

    Verificare cu d · d ≤ n.

    ușoară
  • suma-divizori#376

    Divizorii în perechi (d, n/d).

    ușoară
  • cmmdc#58

    Euclid prin împărțiri.

    ușoară
  • cmmmc#59

    a / cmmdc * b — în ordinea asta, ca să nu depășești.

    ușoară

Temă

Rezolvă-le singur și bifează ce ai terminat. Bifele rămân salvate în acest browser.

  • numarul-de-divizori#18

    Citire din fișier (vezi lecția de fișiere sau cere-mi șablonul).

    ușoară
  • primeintreele#60

    ușoară
  • afisaredivizoricomuni#61

    ușoară
  • urmatorul-prim#375

    ușoară
  • numarperfect#64

    ușoară
  • numarul-divizorilor-pari#388

    ușoară
  • fractii#391

    Simplificarea fracțiilor cu cmmdc.

    ușoară
  • suma-divizorilor-impari#387

    ușoară

Pentru cei care vor mai mult

  • prietene#1574

    ușoară
  • pseudoperfect#445

    ușoară

Grile din subiectele de BAC

Exerciții de tip grilă din variantele de Bacalaureat. Se rezolvă pe pbinfo.ro, care îți verifică imediat răspunsul.

Citește și exersează în plus

Te-ai blocat la lecția asta?

Scrie-mi ce nu iese și vedem împreună de unde se blochează.

Răspunsuri

Exersează pe hârtie

1. 6. Perechile (a, b): (12, 30) → (12, 18) → (12, 6) → (6, 6). Algoritmul calculează cmmdc(12, 30) = 6.

2. 4: numerele 4, 9, 25, 49 (pătratele numerelor prime 2, 3, 5, 7). Un număr cu exact trei divizori este p², cu p prim: divizorii sunt 1, p, p².

3. 36 are 9 divizori: 1, 2, 3, 4, 6, 9, 12, 18, 36. Numărul e impar pentru că 36 este pătrat perfect: divizorul 6 nu are pereche diferită.

4. Euclid: (84, 36) → (36, 12) → (12, 0): cmmdc = 12. cmmmc = 84 / 12 · 36 = 7 · 36 = 252.

5. 8 execuții (d = 2, 3, 4, 5, 6, 7, 8, 9; la d = 10 avem 100 > 97). Niciunul nu divide pe 97, deci 97 este prim.

6. Prin împărțiri: 18 (b e 0 din start, deci bucla nu se execută). Prin scăderi: buclă infinită (a ≠ b mereu, b − a se menține 0).

7. cmmdc(45, 60) = 15, deci 45/60 = 3/4.

8. 28: 1 + 2 + 4 + 7 + 14 = 28. Pentru 12: 1 + 2 + 3 + 4 + 6 = 16 ≠ 12.

9.

#include <iostream>
using namespace std;

int main()
{
    long long n;
    int nr = 0;
    cin >> n;
    for (long long d = 1; d * d <= n; d++)
        if (n % d == 0)
        {
            nr++;
            if (d != n / d) nr++;
        }
    cout << nr;
    return 0;
}

d * d poate depăși int pentru n aproape de 2·10⁹ (de exemplu d = 46 341 dă 2 147 488 281 > 2 147 483 647), deci d și n trebuie să fie long long.