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

Ora 3: Divizori și multipli ai unui număr

Ce vei învăța astăzi: Divizorii, numerele perfecte, numerele prime

Rezultat practic: Determini divizorii unui număr, numerele perfecte și proprietatea de număr prim (Competența 2.2).

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

Înainte de a începe

De ce contează? Divizorii apar peste tot în practică: împărțirea corectă a obiectelor, recunoașterea numerelor prime și a numerelor perfecte. Tot de aici pornește algoritmul lui Euclid și descompunerea în factori primi.

Ce știi deja?

Știi să folosești bucla while pentru cifre. Știi cum funcționează o buclă for cu range(start, stop) în Python? Gândește-te ce numere generează for d in range(1, 7).

Ideea-cheie: d este divizor al lui n (d îl împarte pe n exact, fără rest) dacă n % d == 0; un număr prim are exact 2 divizori (1 și el însuși), iar un număr perfect este egal cu suma divizorilor proprii (a divizorilor mai mici decât numărul, fără numărul însuși).
SINTEZĂ TEORETICĂ ȘI EXEMPLE GHIDATE

Ce vei învăța astăzi?

După această lecție vei ști să afli divizorii unui număr, să numări divizorii și să recunoști numerele perfecte și numerele prime.

Ce este un divizor
Obținerea tuturor divizorilor cu for
Numărul de divizori (contor)
Numere perfecte
Numere prime

Ce este un divizor?

Definiție: Un număr d este divizor al lui n dacă împărțirea lui n la d se face exact, adică restul este 0: n % d == 0.

De exemplu, divizorii lui 12 sunt: 1, 2, 3, 4, 6, 12.

Analogie

Imaginează-ți că trebuie să împarți 12 bomboane în pungi egale, fără să rămână bomboane. Poți folosi pungi de 1, 2, 3, 4, 6 sau 12 bomboane - acestea sunt exact divizorii lui 12.

Obținerea tuturor divizorilor

Definiție: Pentru a afișa toți divizorii lui n parcurgem cu o buclă for toate numerele de la 1 la n și le verificăm pe fiecare: dacă n % d == 0, atunci d este divizor.

Exemplu: divizorii lui 12

ALGORITMUL Afișarea divizorilor lui n citește n pentru d <- 1, n execută dacă n % d = 0 atunci scrie d sfârșit pentru
Python - afișarea divizorilor lui 12
n = 12
for d in range(1, n + 1):
    if n % d == 0:
        print(d, end=" ")

Observă: bucla merge de la 1 la n (inclusiv), iar afișarea se face pe aceeași linie cu end=" ". Rezultatul: 1 2 3 4 6 12.

Numărul de divizori și numerele prime

Definiție: Numărul de divizori ai lui n se obține cu un contor: îl creștem cu 1 de fiecare dată când găsim un divizor.

Un număr este prim dacă are exact 2 divizori: pe 1 și pe el însuși. Exemple: 2, 3, 5, 7, 11.

Număr Divizorii Număr de divizori Este prim?
7 1, 7 2 DA
12 1, 2, 3, 4, 6, 12 6 NU
1 1 1 NU

Optimizare

Pentru probleme mari nu trebuie să verificăm toate numerele până la n. Este suficient până la n // 2 (jumătate), sau chiar până la sqrt(n) (radicalul lui n), pentru că divizorii vin în perechi.

Numerele perfecte

Definiție: Un număr este perfect dacă este egal cu suma divizorilor săi proprii (divizorii mai mici decât el, adică fără numărul însuși).

Exemple: 6 = 1 + 2 + 3 și 28 = 1 + 2 + 4 + 7 + 14 sunt numere perfecte.

Exemplu: verificăm dacă 28 este perfect

Python - verificarea numărului perfect
n = 28
s = 0
for d in range(1, n // 2 + 1):
    if n % d == 0:
        s = s + d
if s == n:
    print("PERFECT")
else:
    print("NU ESTE PERFECT")

Observă: suma divizorilor proprii se calculează doar până la n // 2, pentru că n nu poate avea alt divizor propriu mai mare.

Exercițiu de completare

Completează afirmațiile despre divizori cu cuvintele potrivite:

Un număr d este divizor al lui n dacă restul împărțirii este 0, adică n ______ d == ______. Obținem toți divizorii cu o buclă ______ de la 1 la n. Un număr perfect este egal cu ______ divizorilor săi proprii.

Bancă de cuvinte:
% 0 for sumă

Test de înțelegere

Test rapid - divizori:

1. Divizorii numărului 6 sunt:

2. Numărul 28 este un număr:

3. Un număr prim are exact:

Test de înțelegere - suplimentar

Test rapid suplimentar - divizori și multipli:

1. Divizorii numărului 10 sunt:

2. Cel mai mare divizor propriu al lui 12 este:

3. Numărul 6 este perfect pentru că:

Ai grijă la: numărul 1 nu este prim (are un singur divizor), iar la suma divizorilor proprii nu-l include pe n însuși: bucla merge doar până la n // 2.

Aprofundare

Divizorii vin în perechi: dacă d este divizor al lui n, atunci și n // d este divizor. De exemplu, pentru n = 12: 1 și 12, 2 și 6, 3 și 4. De aceea este suficient să căutăm până la sqrt(n) (radicalul lui n) și să afișăm câte doi divizori la fiecare găsit. Pentru pătrate perfecte (ex: 36), divizorul din mijloc (6) se afișează o singură dată.

Numărul de divizori: dacă n se descompune în factori primi ca n = p1^e1 * p2^e2 * ... * pk^ek, atunci numărul total de divizori este (e1+1) * (e2+1) * ... * (ek+1). De exemplu, 12 = 2^2 * 3^1, deci are (2+1) * (1+1) = 6 divizori.

Numerele prime mari: pentru a verifica dacă n este prim, parcurgem divizorii doar până la int(n ** 0.5); dacă nu găsim niciun divizor, n este prim. Această variantă este extrem de rapidă chiar și pentru numere cu 10-12 cifre.

Cazurile speciale 0 și 1: numărul 1 are un singur divizor (pe 1), deci nu este prim. Numărul 0 are o infinitate de divizori, iar problemele îl exclud de obicei din restricții. La afișarea divizorilor în ordine crescătoare cu optimizarea pe perechi, trebuie să sortăm lista obținută sau să afișăm întâi perechea mică și apoi cea mare.

Aplicație în viața reală: divizorii apar la ambalarea produselor în pachete egale, la împărțirea echitabilă a obiectelor între persoane și la tăierea materialelor în bucăți egale fără resturi. În criptografie, numerele prime mari cu divizori greu de găsit stau la baza securizării datelor.

APLICARE ȘI REZOLVARE DE PROBLEME

PbInfo - 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, pe aceeași linie.

Date de intrare:

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

Date de ieșire:

Programul va afișa pe ecran divizorii lui n, separați prin spații.

Restricții și precizări:

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

Exemplu:

Intrare:

12

Ieșire:

1 2 3 4 6 12
Cum gândim soluția:
  1. Citim numărul n cu input()
  2. Parcurgem cu for toate numerele de la 1 la n
  3. Dacă n % i == 0, afișăm pe i cu end=" "
Scrie soluția în Python:
Soluție corectă:
n = int(input())

for i in range(1, n + 1):
    if n % i == 0:
        print(i, end=" ")

Ce învățăm: o buclă for cu o condiție if ne permite să selectăm exact elementele care respectă o proprietate.

PbInfo - Număr perfect

Enunț:

Cerință: Se citește un număr natural n. Să se afișeze "DA" dacă n este perfect, altfel "NU".

Date de intrare:

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

Date de ieșire:

Programul va afișa pe ecran "DA" sau "NU".

Restricții și precizări:

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

Exemplu:

Intrare:

6

Ieșire:

DA
Cum gândim soluția:
  1. Calculăm suma divizorilor proprii cu o buclă for până la n // 2
  2. Comparăm suma cu n
  3. Afișăm "DA" dacă sunt egale, altfel "NU"
Scrie soluția în Python:
Soluție corectă:
n = int(input())
s = 0

for d in range(1, n // 2 + 1):
    if n % d == 0:
        s = s + d

if s == n:
    print("DA")
else:
    print("NU")

Ce învățăm: pentru a verifica un număr perfect calculăm suma divizorilor proprii (până la jumătate) și o comparăm cu numărul.

EXERCIȚII PRACTICE

Exercițiul Practic: Divizorii unui număr

Sarcini de lucru

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

Sarcina 1: Numără divizorii

Cerință: Scrie un program care citește un număr n și afișează numărul de divizori ai lui n, folosind un contor.

Soluție pentru Sarcina 1:
n = int(input())
cnt = 0

for d in range(1, n + 1):
    if n % d == 0:
        cnt = cnt + 1

print(cnt)

Verifică: pentru n = 12 se afișează 6 (divizorii 1, 2, 3, 4, 6, 12).

Sarcina 2: Verifică dacă n este prim

Cerință: Scrie un program care citește un număr n și afișează "PRIM" dacă n este prim (are exact 2 divizori), altfel "NU ESTE PRIM".

Soluție pentru Sarcina 2:
n = int(input())
cnt = 0

for d in range(1, n + 1):
    if n % d == 0:
        cnt = cnt + 1

if cnt == 2:
    print("PRIM")
else:
    print("NU ESTE PRIM")

Verifică: pentru n = 7 se afișează PRIM; pentru n = 12 se afișează NU ESTE PRIM.

Scrie pe caiet - De reținut

Titlul lecției

Divizori și multipli ai unui număr - numere prime și numere perfecte.

Definiția lecției

Lecția ne învață ce sunt divizorii unui număr și cum îi găsim cu o buclă for: d este divizor al lui n dacă n % d == 0, adică împărțirea lui n la d se face exact. Aflăm că un număr prim are exact doi divizori (1 și el însuși), că numărul de divizori se numără cu un contor și că un număr perfect este egal cu suma divizorilor săi proprii. Optimizăm căutarea mergând doar până la n // 2 sau până la radicalul lui n, pentru că divizorii vin în perechi. În viața reală, divizorii apar la împărțirea echitabilă a obiectelor și la ambalarea produselor în pachete egale. De exemplu, 12 bomboane pot fi împărțite exact în pungi de 1, 2, 3, 4, 6 sau 12 bomboane, care sunt tocmai divizorii lui 12.

Definiții esențiale

Algoritmul cheie - pseudocod

ALGORITMUL Afișarea divizorilor lui n citește n pentru d <- 1, n // 2 execută dacă n % d = 0 atunci scrie d sfârșit pentru scrie n // n este întotdeauna divizor al lui n

Algoritmul cheie - cod Python

n = int(input())

for d in range(1, n // 2 + 1):
    if n % d == 0:
        print(d, end=" ")
print(n)

Greșeli comune de evitat

Sfaturi practice și trucuri

Exemplu practic

Vrem să împărțim 30 de bomboane în pungi egale, fără rest; programul afișează toate variantele posibile de pungă:

n = 30
for d in range(1, n // 2 + 1):
    if n % d == 0:
        print(d, end=" ")
print(n)

Rezultatul este 1 2 3 5 6 10 15 30 - exact pachetele egale în care pot fi împărțite bomboanele.