clasa a IX-a · Algoritmi elementari · lecția 11
Descompunerea în factori primi și aplicațiile ei
60 mintoate profilurile
Înainte de lecția asta: IX.10 Divizibilitate: divizori, numere prime, cmmdc și cmmmc
Ce vei ști după lecție
- Descompui un număr în factori primi, eficient (până la √n).
- Afișezi factorii cu exponenții lor.
- Calculezi numărul și suma divizorilor din descompunere.
- Rezolvi probleme cu zerouri la final (factorii 2 și 5) și cu cel mai mare factor prim.
Lecția are și o fișă de lucru, de rezolvat după ce o citești. Mergi la fișă ↓
Clasa a IX-aLecția 11 din 14 · mai sunt 3Urmează: IX.12 · Șiruri recurente (Fibonacci) și prelucrarea secvențelor de valoriVezi toate lecțiile
Cuprins
Fișiere PDF și de lucru
- Lecția în PDF
versiunea de printat
- Fișa de lucru: Divizibilitate, numere prime, cmmdc, factori primi
6 pagini · 100 min
1. Ideea: orice număr e un produs de „cărămizi”
Orice număr natural n ≥ 2 se scrie în mod unic ca produs de puteri de numere prime:
360 = 2³ · 3² · 5¹
Numerele prime sunt „atomii” numerelor, iar descompunerea e „formula chimică”. Din ea citești imediat: numărul de divizori, cmmdc, cmmmc, zerourile de la final. De aceea merită un algoritm separat.
Algoritmul: încercăm divizorii d = 2, 3, 4, …. Cât timp d îl divide pe n, îl împărțim și numărăm de câte ori.
#include <iostream>
using namespace std;
int main()
{
int n, d = 2;
cin >> n;
while (n > 1)
{
int e = 0;
while (n % d == 0) { n /= d; e++; }
if (e > 0) cout << d << ' ' << e << '\n';
d++;
}
return 0;
}Urmărire pentru n = 360:
| d | n înainte | împărțiri reușite | e | n după | se afișează |
|---|---|---|---|---|---|
| 2 | 360 | 360→180→90→45 | 3 | 45 | 2 3 |
| 3 | 45 | 45→15→5 | 2 | 5 | 3 2 |
| 4 | 5 | niciuna | 0 | 5 | — |
| 5 | 5 | 5→1 | 1 | 1 | 5 1 |
Intrare / ieșire:
| Intrare | Ieșire (factor exponent) |
|---|---|
360 |
2 3, 3 2, 5 1 |
12 |
2 2, 3 1 |
97 |
97 1 (număr prim) |
De ce așa?
De ce d este mereu prim când îl divide pe n? Toți factorii mai mici au fost deja eliminați complet. Dacă 4 ar divide ce a rămas din n, atunci 2 l-ar fi divizat mai devreme, dar 2 a fost scos până nu a mai putut. La fel pentru 6 (ar fi implicat 2 și 3) și 9. Deci nu trebuie să testăm dacă d e prim: se alege singur.
De știut
Pentru n = 97 algoritmul de mai sus încearcă d până la 97: puțin, dar pentru un număr prim mare (de exemplu 999 999 937) ar face aproape un miliard de pași. Vezi secțiunea următoare.
2. Varianta eficientă (până la √n)
Observație: după ce am încercat toți d cu d · d ≤ n, ce a rămas din n (dacă e > 1) este un singur factor prim, deoarece două numere prime ≥ d ar avea produsul > n.
#include <iostream>
using namespace std;
int main()
{
long long n, d = 2;
cin >> n;
while (d * d <= n)
{
int e = 0;
while (n % d == 0) { n /= d; e++; }
if (e > 0) cout << d << ' ' << e << '\n';
d++;
}
if (n > 1) cout << n << ' ' << 1 << '\n'; // ultimul factor prim, cu exponentul 1
return 0;
}| n | ce face bucla | rest la final | se afișează |
|---|---|---|---|
| 360 | d = 2: 3 împărțiri; d = 3: 2 împărțiri; n = 5; 4·4 > 5 stop |
5 | 2 3, 3 2, apoi 5 1 |
| 49 | d = 2…6 nu; d = 7: 49→7→1, n = 1 | 1 | 7 2 |
De ce așa?
De ce testăm n > 1 după buclă? Bucla se oprește când d · d > n. Dacă a rămas un n > 1, nu are niciun divizor ≤ √n, deci e prim. Pentru 360, după ce scoatem 2 și 3, rămâne 5 care e prim, dar buclă nu l-a mai testat pentru că 4 · 4 > 5. Așa apare ultimul factor.
La BAC
„Cel mai mare factor prim” al lui n este fie ultimul d găsit, fie restul n > 1 de la final. Este o întrebare clasică de BAC.
3. Aplicații
Numărul de divizori
Dacă n = p₁^e₁ · p₂^e₂ · … · pₖ^eₖ, atunci numărul de divizori este
(e₁ + 1) · (e₂ + 1) · … · (eₖ + 1)
Exemplu: 360 = 2³ · 3² · 5 → (3+1)(2+1)(1+1) = 24 divizori.
De ce așa?
De ce se adună 1 la fiecare exponent? Un divizor ia din fiecare factor prim un exponent de la 0 până la e inclusiv: sunt e + 1 alegeri, independente între factori, deci se înmulțesc. De exemplu, divizorii lui 12 = 2² · 3 sunt 2^a · 3^b cu a ∈ {0, 1, 2}, b ∈ {0, 1}: 3 · 2 = 6 divizori.
#include <iostream>
using namespace std;
int main()
{
long long n, d = 2;
int nrDiv = 1;
cin >> n;
while (d * d <= n)
{
int e = 0;
while (n % d == 0) { n /= d; e++; }
nrDiv *= (e + 1);
d++;
}
if (n > 1) nrDiv *= 2;
cout << nrDiv;
return 0;
}Zerourile de la sfârșitul unui produs
Un zero la final apare dintr-o pereche 2 · 5. Numărul de zerouri = min(nr. factori 2, nr. factori 5). Pentru n! factorii 5 sunt mai puțini decât factorii 2, deci:
int z = 0;
for (long long p = 5; p <= n; p *= 5)
z += n / p; // numere divizibile cu 5, 25, 125, ...Urmărire pentru n = 100: 100/5 = 20, 100/25 = 4, 125 > 100 stop → 24 de zerouri.
De ce așa?
De ce se adună n/5, n/25, n/125? Fiecare multiplu de 5 aduce un factor 5; multiplii de 25 aduc încă unul (au 5²), cei de 125 încă unul, și așa mai departe. Adunând, fiecare număr e numărat de câte ori îl conține pe 5.
cmmdc și cmmmc prin factori
- cmmdc: fiecare factor comun la exponentul minim;
- cmmmc: fiecare factor la exponentul maxim.
Exemplu: 360 = 2³·3²·5 și 324 = 2²·3⁴: cmmdc = 2²·3² = 36; cmmmc = 2³·3⁴·5 = 3240.
(În practică cmmdc se calculează cu Euclid, dar aceasta e explicația din spate.)
4. Greșeli frecvente
| Greșeala | Efect | Corect |
|---|---|---|
uiți if (n > 1) după buclă |
pierzi ultimul factor prim | tratează restul |
int pentru d * d la n mare |
depășire | long long |
d crește și când l-ai putut împărți din nou |
factori sărite | while (n % d == 0), apoi d++ |
afișezi d fără să verifici e > 0 |
afișezi și factori cu exponent 0 | if (e > 0) |
nrDiv *= e în loc de (e + 1) |
număr de divizori greșit | (e + 1) |
5. La BAC
La BAC
Descompunerea în factori primi apare ca idee în grile (numărul divizorilor, zerourile lui n!, „care este cel mai mare factor prim”) și ca algoritm la Subiectul III (probleme de tip „afișați factorii primi ai lui n”, „numărul divizorilor”). Pentru n până la 10⁹ trebuie obligatoriu varianta cu d * d <= n.
6. Exersează pe hârtie
Răspunsurile sunt la final: încearcă întâi singur.
1. Descompune pe hârtie: 84, 1001, 1024, 97.
2. Câți divizori are 1 000 000? (10⁶ = 2⁶ · 5⁶)
3. Câte zerouri are la final 100!? Dar 30!?
4. Ce se afișează pentru n = 12 în algoritmul din secțiunea 1?
5. Care este cel mai mare factor prim al lui 2⁵ · 3 · 7?
6. Calculează cmmdc și cmmmc pentru 360 = 2³·3²·5 și 324 = 2²·3⁴, scriind descompunerile.
7. Pentru ce valori ale lui n între 1 și 30 are n exact 4 divizori? (Indiciu: p³ sau p·q.)
8. Scrie un program care afișează suma factorilor primi distincți ai lui n.
7. Mai departe (pentru cine vrea mai mult)
Ciurul cu factori. Dacă ai de descompus multe numere (de exemplu 10⁶ numere până la 10⁷), nu repeți algoritmul de fiecare dată. Construiești un ciur în care reții pentru fiecare număr cel mai mic factor prim (cmf[i]); apoi descompui orice număr în O(log n): n = n / cmf[n] până la 1. Este o tehnică standard de concurs.
Funcția lui Euler φ(n). Numără câte numere între 1 și n sunt prime cu n. Din descompunere: φ(n) = n · ∏ (1 − 1/p) pentru fiecare factor prim distinct p. Pentru 360: 360 · (1/2) · (2/3) · (4/5) = 96. Este folosită direct în criptografia RSA.
Aritmetica fundamentală. Unicitatea descompunerii pare evidentă, dar nu e valabilă în orice sistem de numere (există mulțimi de numere în care o descompunere nu e unică). În matematica serioasă, studiul acestor sisteme a dus la teoria numerelor moderne.
Factorizare și securitate. Pentru un număr cu sute de cifre, orice algoritm cunoscut durează mai mult decât vârsta universului. Aceasta este exact siguranța cumpărăturilor online.
Rezumat
- Împarte repetat la
d = 2, 3, …cât timp se poate; numără exponentul. - Oprește-te la
d · d ≤ n; restuln > 1e un factor prim. - Număr divizori = ∏ (eᵢ + 1).
- Zerouri la final de n! = suma
n/5 + n/25 + n/125 + …. - cmmdc: exponenți minimi; cmmmc: exponenți maximi.
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.10
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.
- ușoară
factorizare#62
Factor și exponent pentru fiecare factor prim.
https://www.pbinfo.ro/probleme/62/factorizare
- ușoară
descompunere-factori#1319
https://www.pbinfo.ro/probleme/1319/descompunere-factori
- ușoară
Temă
Rezolvă-le singur și bifează ce ai terminat. Bifele rămân salvate în acest browser.
- ușoară
factoriprimi#435
Două numere au exact aceiași factori primi?
https://www.pbinfo.ro/probleme/435/factoriprimi
- ușoară
factzero#439
Zerourile de la finalul lui n!: câți factori de 5?
https://www.pbinfo.ro/probleme/439/factzero
- ușoară
divizoriprimi#443
https://www.pbinfo.ro/probleme/443/divizoriprimi
- ușoară
factoriprimi1#2821
https://www.pbinfo.ro/probleme/2821/factoriprimi1
- ușoară
mediediv#1568
https://www.pbinfo.ro/probleme/1568/mediediv
Pentru cei care vor mai mult
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.
- #1264secvență pe numărul n (Bac 2021)
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=1264
- #814secvență cu while și i = 2 (Bac 2017)
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=814
- #1620care secvențe afișează numărul tuturor divizorilor
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=1620
- #1619câte cifre de 0 are la sfârșit n!
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=1619
- #821x, y, d naturale strict pozitive (Bac 2016)
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=821
Citește și exersează în plus
- Descompunerea în factori primi · pbinfo.ro
https://www.pbinfo.ro/articole/75/descompunerea-in-factori-primi
- Aplicații ale descompunerii în factori primi · pbinfo.ro
https://www.pbinfo.ro/articole/67/aplicatii-ale-descompunerii-in-factori-primi
- Algopedia — descompunerea în factori primi · algopedia.ro
explicații și probleme în română
https://algopedia.ro/
- Python Tutor pentru C++ · pythontutor.com
urmărește cum scade n și cum crește exponentul e
https://pythontutor.com/cpp.html
- CSES — Counting Divisors · cses.fi
aceeași idee, dar pentru mulți n: ce faci când un singur n nu mai e suficient?
https://cses.fi/problemset/task/1713
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. 84 = 2² · 3 · 7; 1001 = 7 · 11 · 13; 1024 = 2¹⁰; 97 este prim (97¹).
2. (6 + 1)(6 + 1) = 49.
3. 100!: 20 + 4 = 24 de zerouri. 30!: 30/5 = 6, 30/25 = 1 → 7 zerouri.
4. 2 2 și 3 1 (12 = 2² · 3), fiecare pe rând nou.
5. 7.
6. cmmdc = 2² · 3² = 36; cmmmc = 2³ · 3⁴ · 5 = 8 · 81 · 5 = 3240. Verificare: 36 · 3240 = 116 640 = 360 · 324.
7. Numerele cu exact 4 divizori sunt de forma p·q (p ≠ q primi) sau p³: 6, 8, 10, 14, 15, 21, 22, 26, 27. (8 = 2³ și 27 = 3³ sunt de forma p³.)
8.
#include <iostream>
using namespace std;
int main()
{
long long n, d = 2, s = 0;
cin >> n;
while (d * d <= n)
{
if (n % d == 0)
{
s += d;
while (n % d == 0) n /= d;
}
d++;
}
if (n > 1) s += n;
cout << s;
return 0;
}