Școala Româno-Britanică
Modulul 3 Clasa a IX-a | Python

Ora 4: Descompunerea în factori primi

Ce vei învăța astăzi: Descompunerea unui număr natural în factori primi

Rezultat practic: Descompui un număr natural în factori primi și afișezi puterile fiecărui factor (Competența 3.2).

Competența 3.2 Săptămâna 14

Înainte de a începe

De ce contează? Descompunerea (scrierea unui număr ca produs de numere prime, de exemplu 12 = 2^2 * 3) este cheia multor calcule: numărul de divizori se obține direct din exponenți (puterile factorilor, de exemplu 2 și 1 în 2^2 * 3), iar CMMDC și CMMMC pot fi deduse din descompunerile numerelor.

Ce știi deja?

De la lecția despre divizori știi că d îl divide pe n dacă n % d == 0. Câți divizori are 12 și care sunt aceștia? Verifică apoi dacă descompunerea 12 = 2^2 * 3 explică numărul găsit.

Ideea-cheie: Împărțim repetat n la 2, 3, 4... cât timp restul este 0 și numărăm de câte ori fiecare divizor îl împarte exact; n scade la fiecare împărțire reușită.
SINTEZĂ TEORETICĂ ȘI EXEMPLE GHIDATE

Ce vei învăța astăzi?

După această lecție vei ști să descompui un număr în factori primi și să afișezi descompunerea sub forma p1^e1 * p2^e2.

Ce sunt factorii primi
Algoritmul de împărțire repetată
Numărarea puterii fiecărui factor
Afișarea descompunerii p1^e1 * p2^e2

Ce sunt factorii primi?

Definiție: Orice număr natural mai mare decât 1 se poate scrie ca produs de numere prime, numite factori primi (numerele prime al căror produs este numărul dat, de exemplu 2 și 3 pentru 12).

De exemplu: 12 = 2 * 2 * 3 = 2^2 * 3, iar 72 = 2^3 * 3^2.

Analogie

Este ca și cum ai desface o cutie de LEGO în cărămizi de bază (blocurile cele mai mici care nu mai pot fi despicate). La fel, orice număr se „desface" în factori primi, care nu mai pot fi împărțiți.

Algoritmul de descompunere

Algoritmul: Începem cu divizorul d = 2. Cât timp n > 1, împărțim pe n la d repetat (într-o buclă interioară) cât timp se împarte exact, numărând puterea (exponentul: de câte ori se repetă factorul, de exemplu 3 în 2^3). Apoi trecem la divizorul următor d = d + 1.

Exemplu: descompunerea lui 72 = 2^3 * 3^2

ALGORITMUL Descompunerea în factori primi citește n d <- 2 cât timp n > 1 execută p <- 0 cât timp n % d = 0 execută n <- n // d p <- p + 1 sfârșit cât timp dacă p > 0 atunci scrie d, "la puterea", p d <- d + 1 sfârșit cât timp
Python - descompunerea în factori primi
n = 72
d = 2
while n > 1:
    p = 0
    while n % d == 0:
        n = n // d
        p = p + 1
    if p > 0:
        print(d, "la puterea", p)
    d = d + 1

Observă: bucla exterioară crește divizorul, iar bucla interioară numără de câte ori se împarte exact. Rezultatul: 2 la puterea 3, 3 la puterea 2.

Pașii algoritmului

Pas Ce facem Exemplu pentru n = 72
1 Pornim cu d = 2 d = 2
2 Împărțim la d cât timp se poate 72 : 2 = 36, 36 : 2 = 18, 18 : 2 = 9
3 Numărăm puterea lui d 2 apare de 3 ori: 2^3
4 Trecem la d = 3 9 : 3 = 3, 3 : 3 = 1, deci 3^2
5 Ne oprim când n devine 1 72 = 2^3 * 3^2

Exercițiu de completare

Completează codul pentru descompunerea în factori primi:

În descompunerea în factori primi începem cu divizorul ______. Folosim o buclă ______ interioară cât timp n ______ d == 0. La fiecare împărțire exactă creștem puterea p, apoi trecem la divizorul următor ______.

Bancă de cuvinte:
2 while % d

Test de înțelegere

Test rapid - factori primi:

1. Factorii primi ai numărului 12 sunt:

2. Descompunerea numărului 36 este:

3. În descompunerea în factori primi începem cu divizorul:

Test de înțelegere - suplimentar

Test rapid suplimentar - factori primi:

1. Descompunerea lui 18 în factori primi este:

2. În timpul descompunerii împărțim pe n la d:

3. Cel mai mare factor prim al lui 30 este:

Ai grijă la: la fiecare împărțire reușită (n % d == 0) trebuie să-l actualizezi pe n cu n = n // d; altfel bucla interioară rulează la nesfârșit și exponentul p crește la infinit.

Aprofundare

De ce funcționează cu d = d + 1, fără să verificăm primalitatea: când ajungem la un divizor compus, toți factorii săi primi mai mici au fost deja extrași din n. De exemplu, la n = 72, divizorul 2 a fost extras complet înainte ca d să ajungă la 4; restul de 9 nu se mai împarte la 4. Astfel, fiecare d care intră efectiv în bucla interioară este prim.

Optimizarea cu pătratul: pentru numere mari, bucla exterioară poate merge doar până la d * d <= n; dacă după această buclă n > 1, atunci n rămas este el însuși un număr prim (factorul prim mare). Astfel evităm milioane de iterații inutile pentru numere cu factori primi mari, cum ar fi 97.

Aplicații: descompunerea în factori primi este folosită la calculul CMMDC și CMMMC prin formule: CMMDC este produsul factorilor comuni la puterea cea mai mică, iar CMMMC este produsul tuturor factorilor la puterea cea mai mare. De asemenea, numărul de divizori se obține din exponenți: (e1+1) * (e2+1) * ....

Cazul n = 1: pentru n = 1, bucla exterioară while n > 1 nu se execută deloc și programul nu afișează nimic. Matematic, 1 nu are factori primi, fiind considerat un caz special separat în probleme.

Exponentul zero: dacă un divizor nu divide pe n, atunci p rămâne 0 și nu afișăm nimic pentru el. Verificarea if p > 0 este esențială pentru a nu afișa puteri nule, care ar fi matematic incorecte.

APLICARE ȘI REZOLVARE DE PROBLEME

PbInfo - Descompunerea în factori primi

Enunț:

Cerință: Se citește un număr natural n. Să se afișeze factorii primi ai lui n, fiecare pe o linie, împreună cu puterea sa.

Date de intrare:

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

Date de ieșire:

Programul va afișa factorii primi, fiecare pe o linie, sub forma "factor putere".

Restricții și precizări:

Numerele citite sunt numere naturale, cu valori mai mici decât 10^9.

Exemplu:

Intrare:

72

Ieșire:

2 3
3 2
Cum gândim soluția:
  1. Pornim cu d = 2 și cât timp n > 1
  2. Într-o buclă interioară împărțim la d cât timp se poate și numărăm puterea p
  3. Dacă p > 0, afișăm "d p"
  4. Trecem la d = d + 1
Scrie soluția în Python:
Soluție corectă:
n = int(input())
d = 2

while n > 1:
    p = 0
    while n % d == 0:
        n = n // d
        p = p + 1
    if p > 0:
        print(d, p)
    d = d + 1

Ce învățăm: o buclă interioară numără puterea fiecărui factor prim, iar o buclă exterioară parcurge divizorii posibili.

PbInfo - Cel mai mare factor prim

Enunț:

Cerință: Se citește un număr natural n. Să se afișeze cel mai mare factor prim al lui n.

Date de intrare:

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

Date de ieșire:

Programul va afișa pe ecran cel mai mare factor prim al lui n.

Restricții și precizări:

Numerele citite sunt numere naturale, cu valori mai mici decât 10^9.

Exemplu:

Intrare:

72

Ieșire:

3
Cum gândim soluția:
  1. Descompunem pe n în factori primi ca la exercițiul anterior
  2. Reținem în variabila max_f ultimul divizor care a împărțit pe n
  3. Afișăm max_f la final
Scrie soluția în Python:
Soluție corectă:
n = int(input())
d = 2
max_f = 2

while n > 1:
    while n % d == 0:
        n = n // d
        max_f = d
    d = d + 1

print(max_f)

Ce învățăm: ultimul factor care împarte numărul este și cel mai mare, așa că îl reținem pe măsură ce îl descoperim.

EXERCIȚII PRACTICE

Exercițiul Practic: Descompunerea în factori primi

Sarcini de lucru

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

Sarcina 1: Numărul total de factori

Cerință: Scrie un program care citește un număr n, descompune n în factori primi și afișează numărul total de factori (inclusiv cei cu puteri, adică suma puterilor).

Soluție pentru Sarcina 1:
n = int(input())
d = 2
total = 0

while n > 1:
    while n % d == 0:
        n = n // d
        total = total + 1
    d = d + 1

print(total)

Verifică: pentru n = 72 = 2^3 * 3^2 se afișează 5 (3 + 2 factori).

Sarcina 2: Afișează descompunerea

Cerință: Scrie un program care citește un număr n și afișează descompunerea în factori primi sub forma a^b*c^d, de exemplu pentru 72: 2^3*3^2.

Soluție pentru Sarcina 2:
n = int(input())
d = 2
rezultat = ""

while n > 1:
    p = 0
    while n % d == 0:
        n = n // d
        p = p + 1
    if p > 0:
        rezultat = rezultat + str(d) + "^" + str(p) + "*"
    d = d + 1

print(rezultat[:-1])

Verifică: pentru n = 72 se afișează 2^3*3^2. Ștergem ultimul caracter "*" cu rezultat[:-1].

Scrie pe caiet - De reținut

Titlul lecției

Descompunerea în factori primi.

Definiția lecției

Lecția ne învață să descompunem un număr natural în factori primi, adică să-l scriem ca produs de numere prime. Algoritmul începe cu divizorul d = 2 și împarte numărul la d cât timp împărțirea este exactă, numărând de câte ori apare fiecare factor; apoi trece la divizorul următor, până când n devine 1. Rezultatul are forma p1^e1 * p2^e2, unde e este puterea (exponentul) factorului. Descompunerea este folosită peste tot: numărul de divizori se obține direct din exponenți cu formula (e1+1) * (e2+1), iar CMMDC și CMMMC se deduc din descompunerile numerelor. De exemplu, 72 = 2^3 * 3^2, deci are (3+1) * (2+1) = 12 divizori.

Definiții esențiale

Algoritmul cheie - pseudocod

ALGORITMUL Descompunerea în factori primi citește n d <- 2 cât timp n > 1 execută p <- 0 cât timp n % d = 0 execută n <- n // d p <- p + 1 sfârșit cât timp dacă p > 0 atunci scrie d, "la puterea", p d <- d + 1 sfârșit cât timp

Algoritmul cheie - cod Python

n = int(input())
d = 2

while n > 1:
    p = 0
    while n % d == 0:
        n = n // d
        p = p + 1
    if p > 0:
        print(d, "la puterea", p)
    d = d + 1

Greșeli comune de evitat

Sfaturi practice și trucuri

Exemplu practic

Descompunem 84 în factori primi pentru a-i afla structura, utilă de exemplu la calculul numărului de divizori:

n = 84
d = 2
while n > 1:
    p = 0
    while n % d == 0:
        n = n // d
        p = p + 1
    if p > 0:
        print(d, "la puterea", p)
    d = d + 1

Programul afișează: 2 la puterea 2, 3 la puterea 1, 7 la puterea 1, adică 84 = 2^2 * 3 * 7.