Pagina Principală
Ora 12

Divizorii unui Număr

Învață să găsești toți divizorii unui număr și să testezi divizibilitatea

40min teorie + 15min probleme PbInfo
Competența 3.3
Sigla liceului
TEORIE - 40 minute

Ce vei învăța astăzi?

După această lecție, vei stăpâni găsirea divizorilor și testarea divizibilității pentru orice număr.

Ce sunt divizorii unui număr
Algoritmul pentru găsirea tuturor divizorilor
Testarea divizibilității cu un număr dat
Numărul de divizori și sumă divizori

Ce sunt Divizorii?

Definiție: Un număr d este divizor al numărului n dacă restul împărțirii lui n la d este 0.

Exemplu: Pentru n=12, divizorii sunt: 1, 2, 3, 4, 6, 12

1
2
3
4
6
12

12 ÷ 1 = 12, 12 ÷ 2 = 6, 12 ÷ 3 = 4, 12 ÷ 4 = 3, 12 ÷ 6 = 2, 12 ÷ 12 = 1

Analogie: Cutii și obiecte

Gândește-te la divizori ca la cutii în care încap exact obiecte fără a rămâne rest:

12 PIXURI

Încap în:

1 cutie cu 12 2 cutii cu 6 3 cutii cu 4
TEST DIVIZIBILITATE

n % d == 0

restul este 0?
PERECHI DE DIVIZORI

1↔12, 2↔6, 3↔4

produsul = n

Cum găsim divizorii unui număr - 3 metode de gândire:

A
Metoda 1: Împărțiri succesive

"Împarte n la toate numerele mai mici"

Pentru fiecare număr d de la 1 la n:

  • Dacă n % d == 0 → d este divizor
  • Altfel → nu este divizor
for d = 1 to n if n % d == 0 print d

✅ Simplu de înțeles ❌ Ineficient pentru numere mari

B
Metoda 2: Perechi de divizori

"Găsește perechile care înmulțite dau n"

Dacă d este divizor, atunci și n/d este divizor!

1
↔
12
2
↔
6
3
↔
4

✅ Optimizat: căutăm doar până la √n ❌ Trebuie ordonat pentru afișare

C
Metoda 3: Pătrate perfecte

"Atenție când d = n/d"

Pentru pătrate perfecte (16, 25, 36), divizorul √n apare o singură dată!

1
2
4
8
16

Exemplu pentru n=16: √16=4, divizori: (1,16), (2,8), (4) - fără pereche!

✅ Tratează toate cazurile ❌ Cod mai complex

Concluzie: Vom folosi metoda perechilor (B) pentru că este optimă și funcționează pentru orice număr. Adăugăm doar verificarea pentru pătrate perfecte din metoda C.

Algoritmul pentru Găsirea Divizorilor

ALGORITM DivizoriCompleti VARIABILE n, d: întreg ÎNCEPUT CITESTE n SCRIE "Divizorii lui ", n, " sunt: " // Parcurgem toate numerele de la 1 la n ┌ PENTRU d ← 1, n EXECUTĂ │ ┌ DACA n % d = 0 ATUNCI │ │ SCRIE d, " " │ └ SFÂRȘIT DACA └■ SFÂRȘIT

Simplu dar ineficient: Pentru n=1000000, face 1 milion de iterații. Folosit doar pentru numere mici.

ALGORITM DivizoriOptim VARIABILE n, d: întreg ÎNCEPUT CITESTE n SCRIE "Divizorii lui ", n, " sunt: " // Parcurgem doar până la √n ┌ PENTRU d ← 1, √n EXECUTĂ │ ┌ DACA n % d = 0 ATUNCI │ │ SCRIE d, " " // Primul divizor │ │ ┌ DACA d ≠ n/d ATUNCI │ │ │ SCRIE n/d, " " // Divizorul pereche │ │ └ SFÂRȘIT DACA │ └ SFÂRȘIT DACA └■ SFÂRȘIT

Optimizare matematică: Dacă d divide pe n, atunci și n/d îl divide. Ne oprim la √n pentru că după aceea divizorii se repetă.

Metodă Număr iterații Pentru n=100 Pentru n=1000000 Recomandare
Până la n n iterații 100 iterații 1.000.000 iterații ❌ Doar pentru n≤1000
Până la √n √n iterații 10 iterații 1000 iterații ✅ Pentru orice n

Exemplu pentru n=36: Metoda 1: 36 iterații, Metoda 2: √36=6 iterații. Divizorii apar în perechi: (1,36), (2,18), (3,12), (4,9), (6,6).

De ce includem <cmath> și când folosim sqrt?

În algoritmul de găsire a divizorilor, trebuie să parcurgem numerele până la rădăcina pătrată a lui n. Pentru aceasta, avem două variante:

Varianta 1: Folosim funcția sqrt() din biblioteca <cmath>

#include <iostream>
#include <cmath>   // pentru sqrt()
using namespace std;

int main() {
    int n;
    cin >> n;
    
    for (int d = 1; d <= sqrt(n); d++) {
        // ... verifică dacă d este divizor
    }
    
    return 0;
}

Varianta 2: Folosim condiția d * d <= n (fără sqrt)

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    for (int d = 1; d * d <= n; d++) {
        // ... verifică dacă d este divizor
    }
    
    return 0;
}

Care este mai bine?

Condiția d * d <= n este de preferat, deoarece:

  • Este mai rapidă: evită apelarea funcției sqrt care calculează o valoare cu virgulă mobilă.
  • Este mai precisă: evită erorile de rotunjire care pot apărea la conversia la întreg.
  • Este mai simplă: nu necesită includerea bibliotecii suplimentare.

Dar atunci de ce se folosește <cmath> în exerciții?

Uneori, în probleme mai complexe, ai nevoie de alte funcții matematice (puteri, logaritmi, etc.) și atunci includerea <cmath> este necesară. În cazul nostru, pentru găsirea divizorilor, putem folosi oricare dintre variante, dar varianta cu d * d <= n este recomandată.

Concluzie: Pentru găsirea divizorilor, folosește condiția d * d <= n în bucla for. Este mai eficientă și nu necesită <cmath>. Totuși, este bine să cunoști și funcția sqrt pentru alte situații.

Exersăm împreună: n = 24

Pas d d * d <= 24? 24 % d == 0? Divizor găsit (d) Divizor pereche (n/d)
Start 1 ✅ 1*1=1 ≤ 24 ✅ 24%1=0 1 24
Pas 1 2 ✅ 2*2=4 ≤ 24 ✅ 24%2=0 2 12
Pas 2 3 ✅ 3*3=9 ≤ 24 ✅ 24%3=0 3 8
Pas 3 4 ✅ 4*4=16 ≤ 24 ✅ 24%4=0 4 6
Pas 4 5 ✅ 5*5=25 ≤ 24? ❌ ❌ 24%5=4 - -
Final - ✓ 6 iterații totale ✓ 4 divizori găsiți Divizori în perechi:
(1,24) (2,12) (3,8) (4,6)

Divizorii lui 24 în ordine crescătoare: 1, 2, 3, 4, 6, 8, 12, 24

Observație importantă: Algoritmul se oprește la d=4 (deoarece 5*5=25>24). Am făcut doar 6 iterații (d=1,2,3,4,5) în loc de 24! Asta este optimizarea.

Exercițiu de completare - Găsirea divizorilor:

Completează codul C++ pentru afișarea divizorilor:
#include <iostream>
#include <cmath> // Pentru sqrt
using namespace ______;
______ main() {
    int n;
    cin >> ______;
    cout << "Divizorii lui " << n << " sunt: ";
    ______ (int d = 1; d * d <= n; d++) { // Parcurgem până la √n
        ______ (n ______ d == 0) {
            cout << d << " "; // Primul divizor
            ______ (d != n / d) { // Evităm dublarea pentru pătrate perfecte
                cout << n / d << " "; // Divizorul pereche
            }
        }
    }
    cout << endl;
    return ______;
}
Bancă de cuvinte:
std int n for if % 0

Test de înțelegere: Care sunt divizorii?

Test rapid:

Câți divizori are numărul 24 și care sunt ei?

Algoritmul pentru n=24 (√24≈4.9):
d=1: 24%1=0 → afișează 1 și 24
d=2: 24%2=0 → afișează 2 și 12
d=3: 24%3=0 → afișează 3 și 8
d=4: 24%4=0 → afișează 4 și 6

Capcane comune și soluții pentru divizori

Greșeli frecvente la găsirea divizorilor:

❌ Uitarea condiției d*d <= n
for (int d = 1; d <= sqrt(n); d++) { // GREȘIT! // sqrt(n) calculează în fiecare iterație }

Soluție: for (int d = 1; d * d <= n; d++) sau int limit = sqrt(n);

❌ Dublarea divizorului pentru pătrate perfecte

Pentru n=16, d=4: n/d=4 → ar afișa 4 de două ori.

if (d != n / d) { // Verificare ESENȚIALĂ! cout << n / d << " "; }
❌ Parcurgerea până la n pentru numere mari

n=10⁶ → 1 milion de iterații vs 1000 iterații cu metoda optimă.

Best Practices pentru divizori:

✅ Folosește întotdeauna metoda până la √n pentru optimizare
✅ Verifică d != n/d pentru a evita dublarea
✅ Testează cu numere mari (10⁶) și cu pătrate perfecte (16, 25, 36)
✅ Folosește for cu d*d <= n în loc de sqrt(n) în condiție
✅ Atenție la n=0 și n=1 - sunt cazuri speciale

Reguli rapide pentru a lucra cu divizori:

Regula 1: Toate numerele au cel puțin 2 divizori

1 și numărul însuși - numerele prime au exact acești 2 divizori.

Exemplu: 7 are divizorii: 1, 7

Excepție: 1 are un singur divizor (1)

Regula 2: Divizorii apar în perechi

Dacă d este divizor, atunci și n/d este divizor.

d
Divizor mic
×
n/d
Divizor mare
=
n
Numărul inițial

Exemplu pentru n=12: 3 × 4 = 12 (3 și 4 sunt divizori perechi)

Regula 3: Pătratele perfecte au număr impar de divizori

√n este divizor, dar nu are pereche (d = n/d).

Exemplu pentru n=16: √16=4, divizori: 1,2,4,8,16 (5 divizori - impar)

Exemplu pentru n=12: √12≈3.46, divizori: 1,2,3,4,6,12 (6 divizori - par)

Test rapid: Dacă √n este întreg → pătrat perfect → număr impar de divizori

Regula 4: Numărul de divizori crește rapid

Numerele mici pot avea mulți divizori, numerele mari pot avea puțini!

NumărDivizoriNumăr de divizori
121,2,3,4,6,126
17 (prim)1,172
241,2,3,4,6,8,12,248
361,2,3,4,6,9,12,18,369

Concluzie: Nu uita să verifici numerele prime (doar 2 divizori)!

PROBLEME PBINFO - 15 minute

PbInfo #7 - Divizorii unui număr

Enunț:

Cerință: Se citește un număr natural n. Să se afișeze toți divizorii lui n în ordine crescătoare.

Date de intrare:

Programul citește de la tastatură numărul n.

Date de ieșire:

Programul va afișa pe ecran toți divizorii lui n, separați prin spațiu, în ordine crescătoare.

Exemplu:

Intrare:

12

Ieșire:

1 2 3 4 6 12

Explicație: 1, 2, 3, 4, 6, 12 sunt divizorii lui 12

Cum gândim soluția:
  1. Citim numărul n
  2. Folosim for (d = 1; d * d <= n; d++)
  3. Dacă n % d == 0:
    • Afișăm d (primul divizor)
    • Dacă d != n/d:
    • Salvăm n/d (pentru afișare mai târziu)
  4. Pentru ordine crescătoare, afișăm divizorii mari la final
Execuție pentru n=16 (pătrat perfect):
d=1: 16%1=0 → afișează 1, salvează 16
d=2: 16%2=0 → afișează 2, salvează 8
d=3: 16%3=1 → ignoră
d=4: 16%4=0 → afișează 4, d==n/d → nu salvează
Afișare finală: Divizori mici: 1 2 4 | Divizori mari: 8 16
Ce trebuie să verifici mereu?
  • Cazul n=1: are un singur divizor (1)
  • Numere prime: au exact 2 divizori (1 și numărul însuși)
  • Pătrate perfecte: au divizorul √n care nu are pereche
  • Condiția d*d <= n pentru optimizare
Scrie soluția în C++:
Soluție corectă:
Varianta fără vector:
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    // Afișăm divizorii mici
    for (int d = 1; d * d <= n; d++) {
        if (n % d == 0) {
            cout << d << " ";
        }
    }
    
    // Afișăm divizorii mari în ordine crescătoare
    for (int d = (int)sqrt(n); d >= 1; d--) {
        if (n % d == 0 && d != n / d) {
            cout << n / d << " ";
        }
    }
    
    return 0;
}

Ce învățăm din această problemă:

  • Optimizare matematică: Ne oprim la √n în loc de n
  • Perechi de divizori: Dacă d divide n, atunci n/d îl divide
  • Ordinea afișării: Divizorii mici, apoi cei mari pentru ordine crescătoare
  • Cazuri speciale: n=1, numere prime, pătrate perfecte
  • Structuri de date: Vector pentru stocarea divizorilor mari

PbInfo #8 - Suma divizorilor

Problemă care calculează suma tuturor divizorilor

Enunț:

Cerință: Se citește un număr natural n. Să se calculeze suma divizorilor lui n.

Date de intrare:

Programul citește de la tastatură numărul n.

Date de ieșire:

Programul va afișa pe ecran suma divizorilor lui n.

Exemplu:

Intrare:

12

Ieșire:

28

Explicație: 1+2+3+4+6+12 = 28

Cum gândim soluția:
  1. Citim numărul n
  2. Inițializăm suma ← 0
  3. Folosim for (d = 1; d * d <= n; d++):
    • Dacă n % d == 0:
    • suma += d (primul divizor)
    • Dacă d != n/d:
    • suma += n/d (divizorul pereche)
  4. Afișăm suma
Cum funcționează pentru n=12:
d=1: 12%1=0 → suma=0+1+12=13
d=2: 12%2=0 → suma=13+2+6=21
d=3: 12%3=0 → suma=21+3+4=28
REZULTAT: 28 ✓ (1+2+3+4+6+12)
De ce această problemă este mai ușoară?

Pentru că nu trebuie să păstrăm ordinea! Adunăm divizorii imediat ce îi găsim:

  1. Nu avem vectori - doar o sumă
  2. Nu contează ordinea - suma este comutativă
  3. Nu avem afișare complexă - doar un număr

Formula cheie: suma += d + (d != n/d ? n/d : 0)

Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    int suma = 0;
    
    for (int d = 1; d * d <= n; d++) {
        if (n % d == 0) {
            suma += d;  // Adaugă divizorul mic
            
            // Adaugă divizorul mare dacă e diferit
            if (d != n / d) {
                suma += n / d;
            }
        }
    }
    
    cout << suma;
    
    return 0;
}
Varianta alternativă (mai scurtă):
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    int suma = 0;
    
    for (int d = 1; d * d <= n; d++) {
        if (n % d == 0) {
            suma += d;
            suma += (d == n / d ? 0 : n / d);
        }
    }
    
    cout << suma;
    
    return 0;
}

Ce învățăm din această problemă:

  • Optimizare: Același algoritm ca pentru găsirea divizorilor
  • Simplificare: Nu e nevoie de vectori pentru sumă
  • Cazuri speciale:
  • n=1 → suma=1
  • Numere prime → suma = 1 + n
  • Pătrate perfecte → atenție la dublare
  • Operație ternară: Folosirea lui ?: pentru cod compact

PbInfo Bonus - Numărul de divizori ai unui număr

Pentru cei care vor o provocare în plus

Enunț:

Cerință: Se citește un număr natural n. Să se afișeze câți divizori are numărul n.

Date de intrare:

Programul citește de la tastatură numărul n.

Date de ieșire:

Programul va afișa pe ecran numărul de divizori ai lui n.

Exemplu:

Intrare:

12

Ieșire:

6

Explicație: 12 are divizorii 1, 2, 3, 4, 6, 12 (6 divizori)

Cum gândim soluția:
  1. Citim numărul n
  2. Inițializăm contor ← 0
  3. Folosim for (d = 1; d * d <= n; d++):
    • Dacă n % d == 0:
    • contor++ (pentru divizorul mic)
    • Dacă d != n/d:
    • contor++ (pentru divizorul mare)
  4. Afișăm contorul
Cum funcționează pentru n=16 (pătrat perfect):
d=1: 16%1=0 → contor=0+1+1=2 (1 și 16)
d=2: 16%2=0 → contor=2+1+1=4 (2 și 8)
d=3: 16%3=1 → ignoră
d=4: 16%4=0 → contor=4+1=5 (doar 4, d==n/d)
REZULTAT: 5 divizori ✓ (1,2,4,8,16)
De ce această problemă este importantă?

Numărul de divizori este o proprietate fundamentală a numerelor:

  1. Numere prime: 2 divizori (1 și numărul însuși)
  2. Pătrate perfecte: număr impar de divizori
  3. Numere compuse: număr par de divizori (cel puțin 4)

Formula cheie: contor += (d != n/d) ? 2 : 1

Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    int contor = 0;
    
    for (int d = 1; d * d <= n; d++) {
        if (n % d == 0) {
            // Am găsit un divizor d
            contor++;
            
            // Dacă d și n/d sunt diferiți, mai avem un divizor
            if (d != n / d) {
                contor++;
            }
        }
    }
    
    cout << contor;
    
    return 0;
}
Varianta alternativă (mai scurtă):
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    int contor = 0;
    
    for (int d = 1; d * d <= n; d++) {
        if (n % d == 0) {
            // Adaugă 2 divizori dacă sunt diferiți, 1 dacă sunt egali
            contor += (d == n / d) ? 1 : 2;
        }
    }
    
    cout << contor;
    
    return 0;
}

Ce învățăm din această problemă:

  • Optimizare: Același algoritm ca pentru găsirea divizorilor
  • Număr impar vs par: Pătratele perfecte au număr impar de divizori
  • Cazuri speciale:
  • n=1 → 1 divizor
  • Numere prime → 2 divizori
  • Pătrate perfecte → număr impar de divizori
  • Teste recomandate:
  • n=12 → 6 divizori
  • n=16 → 5 divizori (impar!)
  • n=17 → 2 divizori (prim)
  • n=100 → 9 divizori (100=10, pătrat perfect)
Execuție pentru n=18:
d=1: 18%1=0 → contor=0+2=2 (1 și 18)
d=2: 18%2=0 → contor=2+2=4 (2 și 9)
d=3: 18%3=0 → contor=4+2=6 (3 și 6)
d=4: 18%4=2 → ignoră
REZULTAT: 6 divizori ✓ (1,2,3,6,9,18)
EXERCIȚII PRACTICE - 10 minute

Exercițiul Practic: Divizori și Proprietăți

Sarcini de lucru

Completează următoarele sarcini pentru a-ți consolida cunoștințele despre divizori

Sarcina 1: Analiză algoritm divizori

Analizează algoritmul pentru găsirea divizorilor:

Pentru n=36, câte iterații face algoritmul optim (până la √n) vs algoritmul simplu (până la n)?

Soluție pentru Sarcina 1:

Analiza pentru n=36:

  • Algoritmul simplu (până la n):
  • Parcurge toate numerele de la 1 la 36
  • Face 36 de iterații
  • Verifică pentru fiecare număr: 36%1, 36%2, ..., 36%36
  • Algoritmul optim (până la √n):
  • √36 = 6
  • Parcurge numerele de la 1 la 6
  • Face doar 6 iterații
  • La fiecare divizor găsit, afișează și perechea sa
  • Raport de optimizare: 36/6 = 6 ori mai rapid!

Divizorii lui 36 în perechi: (1,36), (2,18), (3,12), (4,9), (6,6)

Concluzie: Pentru numere mari, algoritmul optim este esențial!

Sarcina 2: Implementare în C++ pentru divizori proprii

Cerință: Implementează în C++ un program care citește n și afișează divizorii proprii (excluzând 1 și n).

Soluție pentru Sarcina 2:
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector divizoriProprii;
    
    // Parcurgem de la 2 la n-1
    for (int d = 2; d * d <= n; d++) {
        if (n % d == 0) {
            // Dacă d este divizor propriu și diferit de 1
            if (d != 1) {
                divizoriProprii.push_back(d);
            }
            
            // Dacă n/d este divizor propriu și diferit de n și d
            if (n / d != n && n / d != d && n / d != 1) {
                divizoriProprii.push_back(n / d);
            }
        }
    }
    
    if (divizoriProprii.empty()) {
        cout << "Nu are divizori proprii";
    } else {
        cout << "Divizorii proprii sunt: ";
        for (int divizor : divizoriProprii) {
            cout << divizor << " ";
        }
    }
    
    cout << endl;
    return 0;
}

Explicații importante:

  • Divizorii proprii: Divizori diferiți de 1 și n
  • Pornește de la 2: Sărim peste 1
  • Verificări multiple: Evităm să includem 1 și n
  • Numere prime: Nu au divizori proprii
  • Teste recomandate:
  • n=12 → divizori proprii: 2, 3, 4, 6
  • n=17 (prim) → "Nu are divizori proprii"
  • n=4 → divizori proprii: 2
  • n=1 → niciun divizor propriu

Descarcă toate exercițiile și soluțiile