Parcurgerea divizorilor, numere perfecte și descompunerea în factori primi.
Explici relația de divizibilitate și noțiunea de divizor.
Determini divizorii prin parcurgere directă și prin perechi până la √n.
Stabilești dacă un număr este prim sau compus.
Realizezi descompunerea în factori primi și compari eficiența soluțiilor.
Dacă d divide n, ce alt divizor obținem automat?
Spunem că un număr natural a este divizibil cu un număr natural nenul b dacă împărțirea lui a la b are restul 0. Notăm b | a și spunem că b este divizor al lui a.
De exemplu, 4 | 20 deoarece 20 = 4 · 5. În schimb, 6 ∤ 20 deoarece 20 = 6 · 3 + 2.
Metoda directă verifică valorile 1,2,...,n. Metoda mai eficientă folosește perechile: dacă d | n, atunci n // d | n. Pentru 36 apar perechile (1,36), (2,18), (3,12), (4,9), (6,6), deci este suficient să verificăm candidații până la √n.
Un număr natural n > 1 este prim dacă are exact doi divizori pozitivi: 1 și n. Un număr mai mare decât 1 care nu este prim este compus.
Un număr este perfect dacă este egal cu suma divizorilor săi proprii. Exemple clasice sunt 6 și 28.
Descompunerea exprimă numărul ca produs de numere prime. De exemplu, 84 = 2 · 2 · 3 · 7 = 2² · 3 · 7.
24 de obiecte pot fi aranjate în rânduri cu 1, 2, 3, 4, 6, 8, 12 sau 24 obiecte pe rând. Aceste valori sunt divizorii lui 24.
Dacă descoperim perechea 3 × 8, nu mai trebuie să căutăm separat 8. Acesta este motivul pentru care metoda până la √n este mai eficientă.
Pentru n = 36, dacă d = 4, care este divizorul asociat?
from math import isqrt
n = 36
divizori = []
for d in range(1, isqrt(n) + 1):
if n % d == 0:
divizori.append(d)
if d != n // d:
divizori.append(n // d)
divizori.sort()
print(divizori)from math import isqrt
n = 97
prim = n > 1
for d in range(2, isqrt(n) + 1):
if n % d == 0:
prim = False
break
print(prim)n = 84
factori = []
d = 2
while d * d <= n:
while n % d == 0:
factori.append(d)
n //= d
d += 1
if n > 1:
factori.append(n)
print(factori)Rezultatul este [2, 2, 3, 7], adică 84 = 2² · 3 · 7.
citește n
pentru d 1, √n execută
dacă n mod d = 0 atunci
scrie d
dacă d ≠ n div d atunci
scrie n div d
sfârșit dacă
sfârșit dacă
sfârșit pentrucitește n
prim ← n > 1
pentru d 2, √n execută
dacă n mod d = 0 atunci
prim ← FALS
oprește parcurgerea
sfârșit dacă
sfârșit pentru
scrie primcitește n
m ← n
d ← 2
cât timp d · d ≤ m execută
cât timp m mod d = 0 execută
scrie d
m ← m div d
sfârșit cât timp
d ← d + 1
sfârșit cât timp
dacă m > 1 atunci scrie mAre un singur divizor pozitiv.
Dacă există un divizor propriu mai mare decât √n, există unul asociat mai mic decât √n.
Pentru d = n // d nu adăugați de două ori același divizor.
Algoritmii de divizori și factori primi trebuie aplicați pe valori pentru care cerința este definită; tratați explicit cazurile speciale.
Se citește n. Afișați toți divizorii în ordine crescătoare, precizați dacă n este prim sau compus și afișați descompunerea în factori primi.
Pentru divizori folosim perechi până la √n. Pentru primalitate căutăm un divizor propriu între 2 și √n. Pentru factorizare împărțim repetat la fiecare candidat cât timp împărțirea este exactă.
from math import isqrt
n = int(input("n = "))
divizori = []
for d in range(1, isqrt(n) + 1):
if n % d == 0:
divizori.append(d)
if d != n // d:
divizori.append(n // d)
divizori.sort()
print("Divizori:", divizori)
prim = n > 1
for d in range(2, isqrt(n) + 1):
if n % d == 0:
prim = False
break
print("Numărul este prim." if prim else "Numărul este compus.")
m = n
factori = []
d = 2
while d * d <= m:
while m % d == 0:
factori.append(d)
m //= d
d += 1
if m > 1:
factori.append(m)
print("Factori primi:", factori)| m | d | acțiune |
|---|---|---|
| 84 | 2 | 84 % 2 = 0 → factor 2; m devine 42 |
| 42 | 2 | 42 % 2 = 0 → factor 2; m devine 21 |
| 21 | 3 | 21 % 3 = 0 → factor 3; m devine 7 |
| 7 | 4 | 4·4 > 7; rămâne factorul prim 7 |
Testați 2, 1, 36, 84, un număr prim mare și un pătrat perfect. Pentru 84 rezultatul este divizorii [1,2,3,4,6,7,12,14,21,28,42,84], compus, factori [2,2,3,7].
Produsul factorilor este 2·2·3·7 = 84, iar fiecare divizor afișat divide exact 84.
Realizează o aplicație Python care primește n și afișează divizorii, numărul de divizori, primalitatea, dacă este perfect și descompunerea în factori primi.
divizori, este_prim și factori_primi.este_perfect.Recitește explicațiile și verifică rezultatele înainte de a marca lecția.