Python — Partea 2 — Prelucrarea numerelor și algoritmi numerici

🎯 Cum se folosește această pagină

Pagina este o continuare a Părții 1 și se concentrează exclusiv pe algoritmi de prelucrare a numerelor. Pentru fiecare capitol există mai întâi o explicație a ideii, apoi exact 20 de probleme rezolvate.

Structura fiecărei rezolvări: enunțul complet este repetat în secțiunea „Rezolvare”, apoi urmează ideea algoritmului, pașii, codul Python și un exemplu de urmărire.

Observație pedagogică: problemele sunt intenționat mai dificile decât exemplele introductive. Ele folosesc concepte deja introduse în Partea 2: while, for, range(), operații cu cifre, divizori, multipli și conversii între baze.

1. Prelucrarea numerelor — 20 2. Cifrele unui număr — 20 3. Divizori și multipli — 20 4. CMMDC — 20 5. Factori primi — 20 6. Baze de numerație — 20

1. Prelucrarea numerelor

Lucrăm cu numere întregi folosind operațiile aritmetice și buclele. Accentul este pe construirea și transformarea numerelor fără conversia lor în șiruri.

Operațiile esențiale

Operație	Rol
`n % 10`	extrage ultima cifră
`n // 10`	elimină ultima cifră
`n * 10 + c`	adaugă cifra c la dreapta
`c * 10**k + n`	poate adăuga o cifră la stânga, dacă k este numărul de cifre al lui n

1. Interschimbarea cifrelor din două numere

Dificil

Enunț

Se citesc două numere naturale a și b. Afișați numărul obținut punând ultima cifră a lui a la începutul lui b, iar ultima cifră a lui b la începutul lui a. Se presupune că ambele numere au cel puțin o cifră.

Rezolvare

Ideea: Extragem ultima cifră cu %, eliminăm cifra cu // și apoi construim noile numere folosind o putere a lui 10.

Pașii algoritmului

Extragem ua = a % 10 și ub = b % 10.
Calculăm pA = 10 ** numărul de cifre ale lui a fără ultima cifră și pB analog.
Construim a nou și b nou.
Afișăm rezultatele.

a = int(input())
b = int(input())

x = a
ca = 0
while x > 0:
    ca = ca + 1
    x = x // 10

x = b
cb = 0
while x > 0:
    cb = cb + 1
    x = x // 10

ua = a % 10
ub = b % 10

a_nou = ub * (10 ** (ca - 1)) + a // 10
b_nou = ua * (10 ** (cb - 1)) + b // 10

print(a_nou, b_nou)

Exemplu de urmărire:

a=348, b=57 → a_nou=534, b_nou=73

2. Eliminarea primei cifre

Dificil

Enunț

Se citește un număr natural n cu cel puțin două cifre. Eliminați prima cifră și afișați numărul rămas.

Rezolvare

Ideea: Aflăm puterea lui 10 corespunzătoare primei cifre și o eliminăm prin restul împărțirii.

Pașii algoritmului

Determinăm numărul de cifre.
Construim p = 10 ** (cifre - 1).
Prima cifră este n // p.
Numărul fără prima cifră este n % p.
Afișăm rezultatul.

n = int(input())

x = n
c = 0
while x > 0:
    c = c + 1
    x = x // 10

p = 10 ** (c - 1)
rezultat = n % p

print(rezultat)

Exemplu de urmărire:

n=58321 → p=10000 → 58321 % 10000 = 8321

3. Adăugarea unei cifre la dreapta

Dificil

Enunț

Se citesc un număr natural n și o cifră c. Construiți numărul obținut prin adăugarea cifrei c la sfârșitul lui n.

Rezolvare

Ideea: Înmulțim n cu 10 și adăugăm cifra.

Pașii algoritmului

Citim n și c.
Deplasăm toate cifrele lui n spre stânga: n * 10.
Adăugăm c.
Afișăm rezultatul.

n = int(input())
c = int(input())

rezultat = n * 10 + c
print(rezultat)

Exemplu de urmărire:

n=427, c=6 → 4270+6=4276

4. Adăugarea unei cifre la stânga

Dificil

Enunț

Se citesc un număr natural n și o cifră c. Construiți numărul obținut prin adăugarea cifrei c la începutul lui n.

Rezolvare

Ideea: Trebuie să mutăm cifra c peste toate cifrele lui n, deci avem nevoie de puterea lui 10 asociată numărului de cifre.

Pașii algoritmului

Numărăm cifrele lui n.
Calculăm p = 10 ** numărul de cifre.
Rezultatul este c * p + n.
Afișăm.

n = int(input())
c = int(input())

x = n
nr_cifre = 0
while x > 0:
    nr_cifre = nr_cifre + 1
    x = x // 10

p = 10 ** nr_cifre
rezultat = c * p + n

print(rezultat)

Exemplu de urmărire:

n=427, c=6 → 6*1000+427=6427

5. Rotirea unui număr cu o cifră spre stânga

Dificil

Enunț

Se citește un număr natural n cu cel puțin două cifre. Mutați prima cifră la sfârșitul numărului.

Rezolvare

Ideea: Separăm prima cifră și restul numărului, apoi punem prima cifră după rest.

Pașii algoritmului

Numărăm cifrele.
Separăm prima cifră cu //.
Separăm restul cu %.
Înmulțim restul cu 10 și adăugăm prima cifră.

n = int(input())

x = n
c = 0
while x > 0:
    c = c + 1
    x = x // 10

p = 10 ** (c - 1)
prima = n // p
rest = n % p

rezultat = rest * 10 + prima
print(rezultat)

Exemplu de urmărire:

n=58321 → prima=5, rest=8321 → 83215

6. Rotirea unui număr cu ultima cifră la început

Dificil

Enunț

Se citește un număr natural n cu cel puțin două cifre. Mutați ultima cifră la începutul numărului.

Rezolvare

Ideea: Extragem ultima cifră și numărul fără ea, apoi punem ultima cifră înmulțită cu puterea potrivită la început.

Pașii algoritmului

Numărăm cifrele.
Extragem ultima cifră.
Eliminăm ultima cifră.
Calculăm puterea lui 10 pentru poziția de început.
Construim rezultatul.

n = int(input())

x = n
c = 0
while x > 0:
    c = c + 1
    x = x // 10

u = n % 10
rest = n // 10
p = 10 ** (c - 1)

print(u * p + rest)

Exemplu de urmărire:

n=58321 → u=1, rest=5832 → 1*10000+5832=15832

7. Inversarea unui număr

Dificil

Enunț

Se citește un număr natural n. Afișați numărul obținut prin scrierea cifrelor lui n în ordine inversă.

Rezolvare

Ideea: Construim rezultatul cifră cu cifră: luăm ultima cifră și o adăugăm la dreapta rezultatului.

Pașii algoritmului

Inițial rezultatul este 0.
Extragem ultima cifră cu % 10.
Adăugăm cifra la rezultat: rezultat = rezultat * 10 + cifra.
Eliminăm cifra din n cu // 10.
Repetăm până când n devine 0.

n = int(input())
rezultat = 0

while n > 0:
    cifra = n % 10
    rezultat = rezultat * 10 + cifra
    n = n // 10

print(rezultat)

Exemplu de urmărire:

n=12040 → cifre procesate 0,4,0,2,1 → rezultatul numeric este 4021

8. Suma și produsul cifrelor

Dificil

Enunț

Se citește un număr natural n. Calculați suma cifrelor și produsul cifrelor sale.

Rezolvare

Ideea: Parcurgem cifrele cu % și // și actualizăm două acumulatoare.

Pașii algoritmului

Pornim suma de la 0 și produsul de la 1.
Extragem fiecare cifră.
O adunăm la sumă și o înmulțim în produs.
Eliminăm cifra.
Afișăm cele două rezultate.

n = int(input())
s = 0
p = 1

while n > 0:
    cifra = n % 10
    s = s + cifra
    p = p * cifra
    n = n // 10

print(s, p)

Exemplu de urmărire:

n=352 → suma=10, produs=30

9. Numărul de cifre pare

Dificil

Enunț

Se citește un număr natural n. Determinați câte dintre cifrele sale sunt pare.

Rezolvare

Ideea: Pentru fiecare cifră verificăm dacă restul împărțirii la 2 este 0.

Pașii algoritmului

Extragem ultima cifră.
Verificăm cifra % 2 == 0.
Dacă este pară, incrementăm contorul.
Eliminăm cifra și continuăm.

n = int(input())
cnt = 0

while n > 0:
    cifra = n % 10
    if cifra % 2 == 0:
        cnt = cnt + 1
    n = n // 10

print(cnt)

Exemplu de urmărire:

n=583204 → cifre pare: 8,2,0,4 → 4

10. Prima cifră pară

Dificil

Enunț

Se citește un număr natural n. Afișați prima cifră pară întâlnită de la stânga la dreapta. Dacă nu există, afișați -1.

Rezolvare

Ideea: Pentru a procesa de la stânga la dreapta putem inversa numărul, apoi îl parcurgem de la stânga în reprezentarea inversată.

Pașii algoritmului

Construim inversul lui n.
Parcurgem cifrele inversului, care corespund ordinii inițiale.
Prima cifră pară găsită este răspunsul.
Dacă nu găsim, păstrăm -1.

n = int(input())

x = n
inv = 0
while x > 0:
    inv = inv * 10 + x % 10
    x = x // 10

raspuns = -1
gasit = False

while inv > 0:
    cifra = inv % 10
    if cifra % 2 == 0 and not gasit:
        raspuns = cifra
        gasit = True
    inv = inv // 10

print(raspuns)

Exemplu de urmărire:

n=7358214 → prima cifră pară de la stânga este 8

11. Cea mai mare cifră

Dificil

Enunț

Se citește un număr natural n. Determinați cea mai mare cifră a lui.

Rezolvare

Ideea: Păstrăm cea mai mare cifră găsită până la momentul curent.

Pașii algoritmului

Inițial luăm prima cifră ca maxim.
Parcurgem restul cifrelor.
Dacă cifra curentă este mai mare, actualizăm maximul.
Afișăm maximul.

n = int(input())

maxim = 0
while n > 0:
    cifra = n % 10
    if cifra > maxim:
        maxim = cifra
    n = n // 10

print(maxim)

Exemplu de urmărire:

n=40627 → maximul este 7

12. A doua cea mai mare cifră distinctă

Dificil

Enunț

Se citește un număr natural n. Determinați a doua cea mai mare cifră distinctă din număr. Dacă există o singură cifră distinctă, afișați -1.

Rezolvare

Ideea: Păstrăm cea mai mare și a doua cea mai mare cifră, având grijă ca ele să fie diferite.

Pașii algoritmului

Pentru fiecare cifră verificăm dacă depășește maximul.
Dacă nu depășește maximul, verificăm dacă este distinctă și mai mare decât al doilea maxim.
La final verificăm dacă al doilea maxim a fost găsit.

n = int(input())

max1 = -1
max2 = -1

while n > 0:
    c = n % 10
    if c > max1:
        if c != max1:
            max2 = max1
        max1 = c
    elif c != max1 and c > max2:
        max2 = c
    n = n // 10

print(max2)

Exemplu de urmărire:

n=918393 → cifre distincte 9,8,3,1 → a doua cea mai mare este 8

13. Verificarea palindromului numeric

Dificil

Enunț

Se citește un număr natural n. Verificați dacă numărul este palindrom, adică se citește la fel de la stânga la dreapta și de la dreapta la stânga.

Rezolvare

Ideea: Construim inversul și îl comparăm cu numărul inițial.

Pașii algoritmului

Salvăm numărul inițial.
Construim inversul.
Comparăm cele două valori.
Afișăm DA sau NU.

n = int(input())
original = n
inv = 0

while n > 0:
    inv = inv * 10 + n % 10
    n = n // 10

if inv == original:
    print("DA")
else:
    print("NU")

Exemplu de urmărire:

n=1221 → inversul este 1221 → DA

14. Diferența dintre suma cifrelor pare și impare

Dificil

Enunț

Se citește un număr natural n. Calculați valoarea absolută a diferenței dintre suma cifrelor pare și suma cifrelor impare.

Rezolvare

Ideea: Folosim două sume separate, în funcție de paritatea cifrei.

Pașii algoritmului

Extragem fiecare cifră.
Dacă este pară o adăugăm la sumaPare.
Altfel o adăugăm la sumaImpare.
Calculăm diferența în modul.

n = int(input())
suma_pare = 0
suma_impare = 0

while n > 0:
    c = n % 10
    if c % 2 == 0:
        suma_pare = suma_pare + c
    else:
        suma_impare = suma_impare + c
    n = n // 10

d = suma_pare - suma_impare
if d < 0:
    d = -d

print(d)

Exemplu de urmărire:

n=583204 → pare=14, impare=16 → diferența=2

15. Numărul obținut prin eliminarea tuturor cifrelor 0

Dificil

Enunț

Se citește un număr natural n. Construiți numărul obținut prin eliminarea tuturor cifrelor 0. Dacă toate cifrele sunt 0, afișați 0.

Rezolvare

Ideea: Construim rezultatul din dreapta spre stânga, folosind o putere de 10 doar când cifra nu este zero.

Pașii algoritmului

Parcurgem cifrele.
Dacă cifra este diferită de 0, o așezăm pe poziția curentă.
Creștem puterea lui 10 numai pentru cifrele păstrate.
Afișăm rezultatul.

n = int(input())
rezultat = 0
p = 1

while n > 0:
    c = n % 10
    if c != 0:
        rezultat = rezultat + c * p
        p = p * 10
    n = n // 10

print(rezultat)

Exemplu de urmărire:

n=1020304 → rezultatul este 1234

16. Inserarea cifrei 9 înaintea fiecărei cifre pare

Dificil

Enunț

Se citește un număr natural n. Construiți un nou număr în care înaintea fiecărei cifre pare din n apare cifra 9. Ordinea cifrelor originale trebuie păstrată.

Rezolvare

Ideea: Procesăm cifrele de la dreapta la stânga și construim rezultatul prin adăugări succesive la dreapta.

Pașii algoritmului

Extragem cifra.
Dacă este pară, introducem mai întâi 9 în rezultatul curent și apoi cifra.
Pentru fiecare cifră trebuie actualizată puterea de 10.
La final obținem numărul în ordinea corectă.

n = int(input())
rezultat = 0
p = 1

while n > 0:
    c = n % 10
    if c % 2 == 0:
        rezultat = 9 * p + rezultat
        p = p * 10
    rezultat = c * p + rezultat
    p = p * 10
    n = n // 10

print(rezultat)

Exemplu de urmărire:

n=246 → rezultatul este 9249269

17. Numărul de cifre consecutive egale

Dificil

Enunț

Se citește un număr natural n. Determinați dacă există două cifre consecutive egale. Afișați DA sau NU.

Rezolvare

Ideea: Comparăm fiecare cifră cu cifra imediat următoare.

Pașii algoritmului

Păstrăm ultima cifră.
Eliminăm cifra curentă și extragem următoarea.
Dacă sunt egale, am găsit perechea.
Continuăm doar cât este necesar.

n = int(input())
gasit = False

if n >= 10:
    precedent = n % 10
    n = n // 10

    while n > 0:
        c = n % 10
        if c == precedent:
            gasit = True
        precedent = c
        n = n // 10

if gasit:
    print("DA")
else:
    print("NU")

Exemplu de urmărire:

n=581133 → există perechea 11 → DA

18. Cea mai lungă serie de cifre egale

Dificil

Enunț

Se citește un număr natural n. Determinați lungimea celei mai lungi secvențe de cifre egale consecutive.

Rezolvare

Ideea: Parcurgem cifrele și menținem lungimea seriei curente și maximul întâlnit.

Pașii algoritmului

Păstrăm cifra precedentă.
Dacă cifra curentă este egală cu precedenta, mărim lungimea seriei.
Altfel resetăm seria la 1.
Actualizăm maximul.

n = int(input())

lungime_max = 1
lungime = 1
precedent = n % 10
n = n // 10

while n > 0:
    c = n % 10
    if c == precedent:
        lungime = lungime + 1
    else:
        lungime = 1

    if lungime > lungime_max:
        lungime_max = lungime

    precedent = c
    n = n // 10

print(lungime_max)

Exemplu de urmărire:

n=12223331 → cea mai lungă serie este 333 → 3

19. Alternanță de paritate

Dificil

Enunț

Se citește un număr natural n. Verificați dacă paritatea cifrelor alternează de la o cifră la următoarea.

Rezolvare

Ideea: Este suficient să comparăm paritatea fiecărei cifre cu paritatea cifrei precedente.

Pașii algoritmului

Extragem ultima cifră.
Pentru următoarea cifră verificăm dacă una este pară și cealaltă impară.
Dacă apar două de aceeași paritate, răspunsul devine NU.

n = int(input())
ok = True

precedent = n % 10
n = n // 10

while n > 0:
    c = n % 10
    if c % 2 == precedent % 2:
        ok = False
    precedent = c
    n = n // 10

if ok:
    print("DA")
else:
    print("NU")

Exemplu de urmărire:

n=2741 → par, impar, par, impar → DA

20. Numărul de tranziții între par și impar

Dificil

Enunț

Se citește un număr natural n. Determinați de câte ori se schimbă paritatea între două cifre consecutive.

Rezolvare

Ideea: Numărăm perechile consecutive care au parități diferite.

Pașii algoritmului

Păstrăm paritatea cifrei precedente.
Extragem următoarea cifră.
Dacă paritățile diferă, incrementăm contorul.
Actualizăm precedenta.

n = int(input())
tranzitii = 0

precedent = n % 10
n = n // 10

while n > 0:
    c = n % 10
    if c % 2 != precedent % 2:
        tranzitii = tranzitii + 1
    precedent = c
    n = n // 10

print(tranzitii)

Exemplu de urmărire:

n=274183 → tranziții: 2→7, 7→4, 4→1, 1→8, 8→3 = 5

2. Cifrele unui număr

Acest capitol dezvoltă parcurgerea cifrelor folosind % 10 și // 10, precum și tehnici de comparare, numărare, acumulare și verificare a proprietăților cifrelor.

Tehnica standard de parcurgere a cifrelor

while n > 0:
    cifra = n % 10
    # prelucrăm cifra
    n = n // 10

Dacă avem nevoie de numărul original după parcurgere, îl salvăm înainte: original = n.

1. Numărul de cifre ale lui n

Dificil

Enunț

Se citește un număr natural n. Determinați numărul de cifre.

Rezolvare

Ideea: Împărțim repetat la 10 până când numărul devine 0.

Pașii algoritmului

Inițializăm contorul cu 0.
La fiecare pas creștem contorul.
Eliminăm ultima cifră prin // 10.
Afișăm contorul.

n = int(input())
cnt = 0

if n == 0:
    cnt = 1
else:
    while n > 0:
        cnt = cnt + 1
        n = n // 10

print(cnt)

Exemplu de urmărire:

n=50720 → 5 cifre

2. Suma cifrelor de pe poziții pare

Dificil

Enunț

Se citește un număr natural n. Considerând pozițiile de la dreapta la stânga numerotate de la 1, calculați suma cifrelor aflate pe poziții pare.

Rezolvare

Ideea: Menținem poziția curentă în timp ce eliminăm cifrele.

Pașii algoritmului

Extragem cifra.
Verificăm dacă poziția este pară.
Adăugăm cifra dacă da.
Creștem poziția și continuăm.

n = int(input())
poz = 1
s = 0

while n > 0:
    c = n % 10
    if poz % 2 == 0:
        s = s + c
    poz = poz + 1
    n = n // 10

print(s)

Exemplu de urmărire:

n=58321 → pozițiile 2 și 4: 2 și 8 → 10

3. Produsul cifrelor nenule

Dificil

Enunț

Se citește un număr natural n. Calculați produsul tuturor cifrelor nenule.

Rezolvare

Ideea: Ignorăm cifra 0 și înmulțim restul cifrelor.

Pașii algoritmului

Produsul începe de la 1.
Extragem fiecare cifră.
Dacă este nenulă, o înmulțim.
Eliminăm cifra.

n = int(input())
p = 1

while n > 0:
    c = n % 10
    if c != 0:
        p = p * c
    n = n // 10

print(p)

Exemplu de urmărire:

n=20304 → 2*3*4=24

4. Câte cifre sunt mai mari decât media cifrelor

Dificil

Enunț

Se citește un număr natural n. Determinați câte cifre sunt strict mai mari decât media aritmetică a cifrelor.

Rezolvare

Ideea: Calculăm întâi numărul de cifre și suma lor, apoi facem o a doua parcurgere.

Pașii algoritmului

Calculăm suma și numărul cifrelor.
Media este suma / număr.
Reluăm numărul inițial.
Numărăm cifrele strict mai mari decât medie.

n = int(input())
original = n
s = 0
cnt = 0

if n == 0:
    cnt = 1
else:
    while n > 0:
        s = s + n % 10
        cnt = cnt + 1
        n = n // 10

media = s / cnt
raspuns = 0

while original > 0:
    c = original % 10
    if c > media:
        raspuns = raspuns + 1
    original = original // 10

print(raspuns)

Exemplu de urmărire:

n=58321 → media=19/5=3.8 → cifrele 5,8,? 3 nu,2 nu,1 nu → 2

5. Prima cifră și ultima cifră

Dificil

Enunț

Se citește un număr natural n. Afișați prima și ultima cifră.

Rezolvare

Ideea: Ultima cifră este n % 10, iar prima se obține prin împărțiri repetate la 10.

Pașii algoritmului

Salvăm ultima cifră.
Împărțim până rămâne o singură cifră.
Afișăm cele două.

n = int(input())
ultima = n % 10

while n >= 10:
    n = n // 10

print(n, ultima)

Exemplu de urmărire:

n=58321 → prima=5, ultima=1

6. Diferența dintre prima și ultima cifră

Dificil

Enunț

Se citește un număr natural n. Calculați valoarea absolută a diferenței dintre prima și ultima cifră.

Rezolvare

Ideea: Determinăm cele două cifre și folosim modulul printr-o condiție.

Pașii algoritmului

Extragem ultima cifră.
Găsim prima cifră.
Calculăm diferența.
Dacă este negativă, schimbăm semnul.

n = int(input())
ultima = n % 10

while n >= 10:
    n = n // 10

prima = n
d = prima - ultima

if d < 0:
    d = -d

print(d)

Exemplu de urmărire:

n=58321 → |5-1|=4

7. Numărul de apariții ale cifrei c

Dificil

Enunț

Se citesc un număr natural n și o cifră c. Determinați de câte ori apare c în n.

Rezolvare

Ideea: Parcurgem toate cifrele și incrementăm contorul când găsim c.

Pașii algoritmului

Extragem ultima cifră.
Comparăm cu c.
Incrementăm dacă sunt egale.
Eliminăm cifra.

n = int(input())
c = int(input())
cnt = 0

while n > 0:
    if n % 10 == c:
        cnt = cnt + 1
    n = n // 10

print(cnt)

Exemplu de urmărire:

n=707207, c=7 → 4 apariții

8. Cifra cu cele mai multe apariții

Dificil

Enunț

Se citește un număr natural n. Determinați cifra care apare cel mai des. Dacă există mai multe, afișați cea mai mare dintre ele.

Rezolvare

Ideea: Numărăm separat aparițiile fiecărei cifre folosind 10 contoare.

Pașii algoritmului

Construim câte un contor pentru fiecare cifră.
Parcurgem n și incrementăm contorul corespunzător.
Parcurgem cifrele 0..9 și păstrăm frecvența maximă.
La egalitate alegem cifra mai mare.

n = int(input())
f0 = f1 = f2 = f3 = f4 = 0
f5 = f6 = f7 = f8 = f9 = 0

while n > 0:
    c = n % 10
    if c == 0: f0 += 1
    elif c == 1: f1 += 1
    elif c == 2: f2 += 1
    elif c == 3: f3 += 1
    elif c == 4: f4 += 1
    elif c == 5: f5 += 1
    elif c == 6: f6 += 1
    elif c == 7: f7 += 1
    elif c == 8: f8 += 1
    else: f9 += 1
    n //= 10

f = [f0,f1,f2,f3,f4,f5,f6,f7,f8,f9]
maxim = 0
raspuns = 0

for c in range(10):
    if f[c] >= maxim:
        maxim = f[c]
        raspuns = c

print(raspuns)

Exemplu de urmărire:

n=11223333 → cifra 3

9. Cea mai mică cifră nenulă

Dificil

Enunț

Se citește un număr natural n. Determinați cea mai mică cifră nenulă. Dacă nu există, afișați -1.

Rezolvare

Ideea: Ignorăm zerourile și păstrăm cel mai mic candidat.

Pașii algoritmului

Pornim cu minimul 10.
Extragem fiecare cifră.
Dacă este nenulă și mai mică decât minimul, o păstrăm.
Dacă minimul a rămas 10, afișăm -1.

n = int(input())
minim = 10

while n > 0:
    c = n % 10
    if c != 0 and c < minim:
        minim = c
    n //= 10

if minim == 10:
    print(-1)
else:
    print(minim)

Exemplu de urmărire:

n=500702 → minim nenul=2

10. Cea mai mare cifră impară

Dificil

Enunț

Se citește un număr natural n. Determinați cea mai mare cifră impară. Dacă nu există, afișați -1.

Rezolvare

Ideea: Verificăm paritatea fiecărei cifre și păstrăm maximul impar.

Pașii algoritmului

Extragem cifra.
Verificăm c % 2 == 1.
Actualizăm maximul.
Afișăm -1 dacă nu am găsit.

n = int(input())
maxim = -1

while n > 0:
    c = n % 10
    if c % 2 == 1 and c > maxim:
        maxim = c
    n //= 10

print(maxim)

Exemplu de urmărire:

n=24682 → nu există cifră impară → -1

11. Cifre în ordine strict crescătoare

Dificil

Enunț

Se citește un număr natural n. Verificați dacă cifrele sale sunt în ordine strict crescătoare de la stânga la dreapta.

Rezolvare

Ideea: Comparăm cifre consecutive. Deoarece le extragem de la dreapta, condiția devine inversată.

Pașii algoritmului

Extragem cifra precedentă.
Extragem următoarea cifră spre stânga.
Pentru ordine crescătoare, cifra din stânga trebuie să fie mai mică decât cea din dreapta.
Dacă o pereche nu respectă regula, răspunsul este NU.

n = int(input())
ok = True

dreapta = n % 10
n //= 10

while n > 0:
    stanga = n % 10
    if stanga >= dreapta:
        ok = False
    dreapta = stanga
    n //= 10

if ok:
    print("DA")
else:
    print("NU")

Exemplu de urmărire:

n=12389 → DA; n=12289 → NU

12. Cifre în ordine descrescătoare

Dificil

Enunț

Se citește un număr natural n. Verificați dacă cifrele sale sunt în ordine strict descrescătoare de la stânga la dreapta.

Rezolvare

Ideea: La parcurgerea de la dreapta, cifra din stânga trebuie să fie mai mare decât cifra din dreapta.

Pașii algoritmului

Extragem ultima cifră.
Comparăm următoarea cifră din stânga cu ea.
Dacă nu este strict mai mare, respingem.

n = int(input())
ok = True

dreapta = n % 10
n //= 10

while n > 0:
    stanga = n % 10
    if stanga <= dreapta:
        ok = False
    dreapta = stanga
    n //= 10

print("DA" if ok else "NU")

Exemplu de urmărire:

n=97531 → DA

13. Număr de cifre distincte

Dificil

Enunț

Se citește un număr natural n. Determinați câte cifre distincte apar în n.

Rezolvare

Ideea: Folosim 10 marcaje booleene, câte unul pentru fiecare cifră.

Pașii algoritmului

Inițial toate marcajele sunt False.
La apariția cifrei c, marcajul ei devine True.
La final numărăm marcajele True.

n = int(input())
f = [False] * 10

while n > 0:
    f[n % 10] = True
    n //= 10

cnt = 0
for c in range(10):
    if f[c]:
        cnt += 1

print(cnt)

Exemplu de urmărire:

n=120320 → cifre distincte 0,1,2,3 → 4

14. Toate cifrele sunt diferite

Dificil

Enunț

Se citește un număr natural n. Verificați dacă toate cifrele lui sunt distincte.

Rezolvare

Ideea: Dacă o cifră apare de două ori, numărul nu respectă cerința.

Pașii algoritmului

Folosim un tablou de frecvențe.
La fiecare cifră verificăm dacă a mai apărut.
Dacă da, afișăm NU.
Altfel marcăm cifra.

n = int(input())
f = [0] * 10
ok = True

while n > 0:
    c = n % 10
    f[c] += 1
    if f[c] > 1:
        ok = False
    n //= 10

print("DA" if ok else "NU")

Exemplu de urmărire:

n=58321 → toate diferite → DA

15. Cea mai lungă cifră repetată consecutiv

Dificil

Enunț

Se citește un număr natural n. Determinați cifra care formează cea mai lungă secvență de apariții consecutive. La egalitate, alegeți cifra mai mare.

Rezolvare

Ideea: Combinăm parcurgerea consecutivă cu păstrarea celui mai bun candidat.

Pașii algoritmului

Păstrăm lungimea seriei curente.
Dacă cifra este egală cu precedenta, mărim seria.
Altfel resetăm seria.
La o serie mai lungă actualizăm cifra; la egalitate alegem cifra mai mare.

n = int(input())
precedent = n % 10
n //= 10
lungime = 1
maxim = 1
raspuns = precedent

while n > 0:
    c = n % 10
    if c == precedent:
        lungime += 1
    else:
        lungime = 1

    if lungime > maxim or (lungime == maxim and c > raspuns):
        maxim = lungime
        raspuns = c

    precedent = c
    n //= 10

print(raspuns, maxim)

Exemplu de urmărire:

n=4411112233 → cifra 1, lungime 4

16. Suma cifrelor dintre prima și ultima apariție a lui c

Dificil

Enunț

Se citesc un număr natural n și o cifră c. Calculați suma cifrelor situate strict între prima și ultima apariție a cifrei c. Dacă c apare de mai puțin de două ori, afișați 0.

Rezolvare

Ideea: Construim inversul pentru a putea identifica ordinea și apoi parcurgem cifrele dintre cele două apariții.

Pașii algoritmului

Determinăm inversul.
Parcurgem cifrele în ordinea inițială.
Începem adunarea după prima apariție a lui c.
Oprim adunarea când întâlnim a doua apariție.

n = int(input())
c = int(input())

inv = 0
x = n
while x > 0:
    inv = inv * 10 + x % 10
    x //= 10

s = 0
activ = False
gasit = False

while inv > 0:
    d = inv % 10
    if d == c:
        if not gasit:
            gasit = True
            activ = True
        else:
            activ = False
    elif activ:
        s += d
    inv //= 10

print(s)

Exemplu de urmărire:

n=52345126, c=5 → între cele două apariții: 2+3+4+1+2+6=18

17. Numărul de cifre care apar exact de două ori

Dificil

Enunț

Se citește un număr natural n. Determinați câte cifre apar exact de două ori în n.

Rezolvare

Ideea: Calculăm frecvențele celor 10 cifre și numărăm frecvențele egale cu 2.

Pașii algoritmului

Construim frecvențele.
Parcurgem cele 10 cifre.
Numărăm exact frecvența 2.

n = int(input())
f = [0] * 10

while n > 0:
    f[n % 10] += 1
    n //= 10

cnt = 0
for c in range(10):
    if f[c] == 2:
        cnt += 1

print(cnt)

Exemplu de urmărire:

n=112233445 → cifrele 1,2,3,4 apar de două ori → 4

18. Cifra lipsă dintre 0 și 9

Dificil

Enunț

Se citește un număr natural n care conține fiecare cifră de la 0 la 9 cel puțin o dată, cu excepția unei singure cifre. Determinați cifra lipsă.

Rezolvare

Ideea: Marcăm cifrele întâlnite și căutăm singura valoare nemarcată.

Pașii algoritmului

Marcăm fiecare cifră.
Parcurgem 0..9.
Afișăm cifra care nu a fost întâlnită.

n = int(input())
f = [False] * 10

while n > 0:
    f[n % 10] = True
    n //= 10

for c in range(10):
    if not f[c]:
        print(c)

Exemplu de urmărire:

dacă n conține toate cifrele în afară de 7 → 7

19. Numărul de cifre care divid pe n

Dificil

Enunț

Se citește un număr natural n. Determinați câte cifre nenule ale lui n sunt divizori ai lui n.

Rezolvare

Ideea: Pentru fiecare cifră nenulă verificăm n % cifra == 0.

Pașii algoritmului

Păstrăm valoarea inițială.
Extragem fiecare cifră.
Ignorăm zero.
Verificăm dacă numărul este divizibil cu cifră.

n = int(input())
original = n
cnt = 0

while n > 0:
    c = n % 10
    if c != 0 and original % c == 0:
        cnt += 1
    n //= 10

print(cnt)

Exemplu de urmărire:

n=128 → cifrele 1,2,8; 128 este divizibil cu 1,2,8 → 3

20. Numărul este format doar din cifre pare

Dificil

Enunț

Se citește un număr natural n. Verificați dacă toate cifrele sale sunt pare.

Rezolvare

Ideea: Căutăm o singură cifră impară. Dacă apare, răspunsul este NU.

Pașii algoritmului

Extragem cifrele.
Dacă una este impară, marcăm eșecul.
La final afișăm DA/NU.

n = int(input())
ok = True

if n == 0:
    ok = True

while n > 0:
    if (n % 10) % 2 == 1:
        ok = False
    n //= 10

print("DA" if ok else "NU")

Exemplu de urmărire:

n=82460 → toate cifrele sunt pare → DA

3. Divizori și multipli

Un divizor al lui n împarte exact numărul n. Un multiplu al lui d are forma k*d. Capitolul construiește treptat algoritmi pentru numărare, sumă, verificare și identificarea divizorilor comuni.

Divizibilitatea

a % d == 0 înseamnă că d este divizor al lui a. În sens invers, a este multiplu al lui d.

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

1. Numărul de divizori ai lui n

Dificil

Enunț

Se citește un număr natural n. Determinați numărul divizorilor pozitivi ai lui n.

Rezolvare

Ideea: Verificăm toate valorile de la 1 la n și numărăm divizorii.

Pașii algoritmului

Parcurgem d de la 1 la n.
Dacă n % d == 0, d este divizor.
Incrementăm contorul.

n = int(input())
cnt = 0

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

print(cnt)

Exemplu de urmărire:

n=12 → divizori 1,2,3,4,6,12 → 6

2. Suma divizorilor proprii

Dificil

Enunț

Se citește n > 1. Calculați suma divizorilor pozitivi ai lui n mai mici decât n.

Rezolvare

Ideea: Parcurgem 1..n-1 și adunăm divizorii.

Pașii algoritmului

Pornim suma de la 0.
Testăm fiecare d.
Adunăm dacă n % d == 0.

n = int(input())
s = 0

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

print(s)

Exemplu de urmărire:

n=12 → 1+2+3+4+6=16

3. Cel mai mare divizor propriu

Dificil

Enunț

Se citește n > 1. Determinați cel mai mare divizor al lui n care este strict mai mic decât n.

Rezolvare

Ideea: Cel mai mare divizor propriu se găsește căutând descrescător.

Pașii algoritmului

Pornim de la n-1.
Coborâm până găsim primul divizor.
Afișăm acel divizor.

n = int(input())
d = n - 1

while n % d != 0:
    d -= 1

print(d)

Exemplu de urmărire:

n=36 → cel mai mare divizor propriu este 18

4. Verificare număr prim

Dificil

Enunț

Se citește n. Verificați dacă n este număr prim.

Rezolvare

Ideea: Un număr prim are exact doi divizori pozitivi: 1 și el însuși.

Pașii algoritmului

Pentru n < 2 răspunsul este NU.
Căutăm un divizor între 2 și n-1.
Dacă găsim unul, n nu este prim.

n = int(input())
prim = True

if n < 2:
    prim = False
else:
    d = 2
    while d < n:
        if n % d == 0:
            prim = False
        d += 1

print("DA" if prim else "NU")

Exemplu de urmărire:

n=29 → nu are divizori între 2 și 28 → DA

5. Numărul de divizori impari

Dificil

Enunț

Se citește n. Determinați câți divizori pozitivi ai lui n sunt impari.

Rezolvare

Ideea: Parcurgem divizorii și testăm paritatea lor.

Pașii algoritmului

Parcurgem 1..n.
Dacă d divide n și d este impar, incrementăm.

n = int(input())
cnt = 0

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

print(cnt)

Exemplu de urmărire:

n=24 → divizori impari 1,3 → 2

6. Toți divizorii lui n

Dificil

Enunț

Se citește n. Afișați toți divizorii pozitivi ai lui n în ordine crescătoare.

Rezolvare

Ideea: Parcurgem de la 1 la n și afișăm valorile care împart exact numărul.

Pașii algoritmului

Parcurgem d.
Verificăm restul.
Afișăm divizorii găsiți.

n = int(input())

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

Exemplu de urmărire:

n=18 → 1 2 3 6 9 18

7. Divizorii în ordine descrescătoare

Dificil

Enunț

Se citește n. Afișați divizorii pozitivi ai lui n în ordine descrescătoare.

Rezolvare

Ideea: Parcurgem de la n la 1.

Pașii algoritmului

Începem cu n.
Scădem d.
Afișăm când n % d == 0.

n = int(input())

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

Exemplu de urmărire:

n=18 → 18 9 6 3 2 1

8. Cel mai mic multiplu al lui a mai mare decât b

Dificil

Enunț

Se citesc a și b, cu a > 0. Determinați cel mai mic multiplu pozitiv al lui a care este strict mai mare decât b.

Rezolvare

Ideea: Căutăm primul multiplu k*a care depășește b.

Pașii algoritmului

Pornim k=1.
Calculăm k*a.
Creștem k până când produsul depășește b.
Afișăm produsul.

a = int(input())
b = int(input())

k = 1
while k * a <= b:
    k += 1

print(k * a)

Exemplu de urmărire:

a=7, b=30 → 35

9. Câte numere din [a,b] sunt divizibile cu d

Dificil

Enunț

Se citesc a, b și d > 0. Determinați câte numere întregi din intervalul [a,b] sunt divizibile cu d.

Rezolvare

Ideea: Parcurgem intervalul și verificăm restul.

Pașii algoritmului

Pornim contorul de la 0.
Pentru fiecare x verificăm x % d == 0.
Incrementăm.

a = int(input())
b = int(input())
d = int(input())

cnt = 0
for x in range(a, b + 1):
    if x % d == 0:
        cnt += 1

print(cnt)

Exemplu de urmărire:

[10,25], d=4 → 12,16,20,24 → 4

10. Suma multiplilor lui d din [a,b]

Dificil

Enunț

Se citesc a, b și d > 0. Calculați suma tuturor multiplilor lui d din [a,b].

Rezolvare

Ideea: Parcurgem intervalul și acumulăm doar multiplii.

Pașii algoritmului

Inițial s=0.
Testăm fiecare x.
Dacă este divizibil cu d, îl adunăm.

a = int(input())
b = int(input())
d = int(input())

s = 0
for x in range(a, b + 1):
    if x % d == 0:
        s += x

print(s)

Exemplu de urmărire:

[5,20], d=3 → 6+9+12+15+18=60

11. Număr perfect

Dificil

Enunț

Se citește n. Verificați dacă n este perfect, adică este egal cu suma divizorilor săi proprii.

Rezolvare

Ideea: Calculăm suma divizorilor strict mai mici decât n.

Pașii algoritmului

Calculăm suma divizorilor proprii.
Comparăm suma cu n.
Afișăm DA/NU.

n = int(input())
s = 0

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

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

Exemplu de urmărire:

28 → 1+2+4+7+14=28 → DA

12. Număr abundent

Dificil

Enunț

Se citește n. Verificați dacă suma divizorilor proprii ai lui n este mai mare decât n.

Rezolvare

Ideea: Este aceeași parcurgere ca la numărul perfect, dar comparăm cu >.

Pașii algoritmului

Calculăm suma.
Verificăm dacă s > n.

n = int(input())
s = 0

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

print("DA" if s > n else "NU")

Exemplu de urmărire:

12 → suma 16 > 12 → DA

13. Număr deficient

Dificil

Enunț

Se citește n. Verificați dacă suma divizorilor proprii este mai mică decât n.

Rezolvare

Ideea: Calculăm suma și verificăm s < n.

Pașii algoritmului

Parcurgem divizorii proprii.
Calculăm suma.
Comparăm.

n = int(input())
s = 0

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

print("DA" if s < n else "NU")

Exemplu de urmărire:

10 → suma 8 < 10 → DA

14. Două numere sunt prietene

Dificil

Enunț

Se citesc a și b. Verificați dacă fiecare este egal cu suma divizorilor proprii ai celuilalt.

Rezolvare

Ideea: Calculăm separat suma divizorilor proprii pentru a și b.

Pașii algoritmului

Calculăm sa pentru a.
Calculăm sb pentru b.
Verificăm sa == b și sb == a.

a = int(input())
b = int(input())

sa = 0
for d in range(1, a):
    if a % d == 0:
        sa += d

sb = 0
for d in range(1, b):
    if b % d == 0:
        sb += d

print("DA" if sa == b and sb == a else "NU")

Exemplu de urmărire:

220 și 284 sunt un exemplu clasic de pereche prietenoasă

15. Cel mai mic divizor mai mare decât 1

Dificil

Enunț

Se citește n > 1. Determinați cel mai mic divizor pozitiv al lui n mai mare decât 1.

Rezolvare

Ideea: Primul divizor găsit începând cu 2 este răspunsul.

Pașii algoritmului

Pornim d=2.
Căutăm până când n % d == 0.
Afișăm d.

n = int(input())
d = 2

while n % d != 0:
    d += 1

print(d)

Exemplu de urmărire:

n=91 → primul divizor >1 este 7

16. Numărul de multipli comuni în [a,b]

Dificil

Enunț

Se citesc a, b, x și y, cu x,y > 0. Determinați câte numere din [a,b] sunt simultan multipli ai lui x și ai lui y.

Rezolvare

Ideea: Un număr este multiplu comun dacă este divizibil și cu x, și cu y.

Pașii algoritmului

Parcurgem intervalul.
Verificăm x % valoare == 0 și y % valoare == 0.
Numărăm valorile.

a = int(input())
b = int(input())
x = int(input())
y = int(input())

cnt = 0
for n in range(a, b + 1):
    if n % x == 0 and n % y == 0:
        cnt += 1

print(cnt)

Exemplu de urmărire:

[1,50], x=6,y=8 → 24,48 → 2

17. Suma divizorilor comuni

Dificil

Enunț

Se citesc a și b. Calculați suma divizorilor pozitivi comuni celor două numere.

Rezolvare

Ideea: Parcurgem până la min(a,b) și verificăm ambele divizibilități.

Pașii algoritmului

Determinăm limita mai mică.
Testăm fiecare candidat.
Adunăm dacă divide ambele.

a = int(input())
b = int(input())

limita = min(a, b)
s = 0

for d in range(1, limita + 1):
    if a % d == 0 and b % d == 0:
        s += d

print(s)

Exemplu de urmărire:

18 și 24 → divizori comuni 1,2,3,6 → suma 12

18. Numărul de divizori comuni

Dificil

Enunț

Se citesc a și b. Determinați numărul divizorilor pozitivi comuni.

Rezolvare

Ideea: Aceeași idee ca la suma divizorilor comuni, dar numărăm.

Pașii algoritmului

Parcurgem 1..min(a,b).
Verificăm divizibilitatea ambelor.
Incrementăm.

a = int(input())
b = int(input())

cnt = 0
for d in range(1, min(a, b) + 1):
    if a % d == 0 and b % d == 0:
        cnt += 1

print(cnt)

Exemplu de urmărire:

18 și 24 → 4 divizori comuni

19. Verificarea unui multiplu

Dificil

Enunț

Se citesc n și k. Verificați dacă n este multiplu de k. Se presupune k > 0.

Rezolvare

Ideea: n este multiplu de k exact atunci când restul împărțirii este 0.

Pașii algoritmului

Calculăm n % k.
Dacă este 0, afișăm DA; altfel NU.

n = int(input())
k = int(input())

if n % k == 0:
    print("DA")
else:
    print("NU")

Exemplu de urmărire:

n=84,k=7 → DA

20. Cel mai mare număr din [a,b] care divide pe n

Dificil

Enunț

Se citesc a, b și n. Determinați cel mai mare număr din [a,b] care este divizor al lui n. Dacă nu există, afișați -1.

Rezolvare

Ideea: Căutăm descrescător în interval și ne oprim la primul divizor.

Pașii algoritmului

Pornim de la b.
Coborâm până la a.
Primul x pentru care n % x == 0 este răspunsul.
Dacă ajungem sub a, afișăm -1.

a = int(input())
b = int(input())
n = int(input())

x = b
raspuns = -1

while x >= a:
    if n % x == 0:
        raspuns = x
        break
    x -= 1

print(raspuns)

Exemplu de urmărire:

a=5,b=30,n=84 → 28 este cel mai mare divizor din interval

4. CMMDC – algoritmul lui Euclid

CMMDC este cel mai mare număr natural care divide simultan două sau mai multe numere. Sunt prezentate ambele forme clasice ale algoritmului lui Euclid: prin scăderi și prin împărțiri cu rest.

Algoritmul lui Euclid

Pentru două numere nenule, înlocuim succesiv perechea (a,b) cu (b, a % b). Când al doilea număr devine 0, primul este CMMDC.

while b != 0:
    r = a % b
    a = b
    b = r

Aceasta este una dintre cele mai importante tehnici algoritmice din capitol: în loc să căutăm toți divizorii comuni, reducem problema prin resturi succesive.

1. CMMDC prin scăderi repetate

Dificil

Enunț

Se citesc două numere naturale nenule. Calculați CMMDC folosind algoritmul lui Euclid prin scăderi repetate.

Rezolvare

Ideea: Cât timp numerele sunt diferite, îl scădem pe cel mai mic din cel mai mare.

Pașii algoritmului

Dacă a>b, înlocuim a cu a-b.
Altfel înlocuim b cu b-a.
Când devin egale, valoarea lor este CMMDC.

a = int(input())
b = int(input())

while a != b:
    if a > b:
        a = a - b
    else:
        b = b - a

print(a)

Exemplu de urmărire:

48 și 18 → 30,18 → 12,18 → 12,6 → 6,6 → 6

2. CMMDC prin împărțiri repetate

Dificil

Enunț

Se citesc a și b. Calculați CMMDC folosind algoritmul lui Euclid cu resturi.

Rezolvare

Ideea: Înlocuim perechea (a,b) cu (b, a%b) până când b devine 0.

Pașii algoritmului

Calculăm restul.
Deplasăm b în a.
Punem restul în b.
Când b=0, a este CMMDC.

a = int(input())
b = int(input())

while b != 0:
    r = a % b
    a = b
    b = r

print(a)

Exemplu de urmărire:

252 și 105 → 105,42 → 42,21 → 21,0 → 21

3. CMMDC a trei numere

Dificil

Enunț

Se citesc trei numere naturale nenule. Determinați CMMDC-ul lor.

Rezolvare

Ideea: Calculăm mai întâi CMMDC(a,b), apoi CMMDC(rezultat,c).

Pașii algoritmului

Aplicăm Euclid pentru a și b.
Rezultatul se combină cu c.
Afișăm rezultatul final.

a = int(input())
b = int(input())
c = int(input())

while b != 0:
    r = a % b
    a = b
    b = r

b = c
while b != 0:
    r = a % b
    a = b
    b = r

print(a)

Exemplu de urmărire:

84,126,210 → CMMDC=42

4. CMMDC și numărul de pași

Dificil

Enunț

Se citesc a și b. Calculați CMMDC și numărul de iterații ale algoritmului lui Euclid cu resturi.

Rezolvare

Ideea: Numărăm de câte ori executăm bucla.

Pașii algoritmului

Inițializăm pașii cu 0.
La fiecare rest calculat creștem contorul.
La final afișăm CMMDC și contorul.

a = int(input())
b = int(input())
pasi = 0

while b != 0:
    r = a % b
    a = b
    b = r
    pasi += 1

print(a, pasi)

Exemplu de urmărire:

48,18 → CMMDC 6; numărul de pași depinde de succesiunea resturilor

5. Verificare coprimalitate

Dificil

Enunț

Se citesc a și b. Verificați dacă sunt prime între ele, adică au CMMDC egal cu 1.

Rezolvare

Ideea: Aplicăm Euclid și verificăm rezultatul.

Pașii algoritmului

Calculăm CMMDC.
Dacă este 1, afișăm DA; altfel NU.

a = int(input())
b = int(input())

while b != 0:
    a, b = b, a % b

print("DA" if a == 1 else "NU")

Exemplu de urmărire:

14 și 25 → CMMDC=1 → DA

6. CMMDC al tuturor numerelor din [a,b]

Dificil

Enunț

Se citesc a și b. Calculați CMMDC-ul tuturor numerelor întregi din intervalul [a,b], presupunând 1 <= a <= b.

Rezolvare

Ideea: Pornim cu CMMDC(a,a+1), apoi combinăm pe rând fiecare număr.

Pașii algoritmului

Inițial d=a.
Pentru fiecare x de la a+1 la b calculăm CMMDC(d,x).
La final d este răspunsul.

a = int(input())
b = int(input())

d = a

for x in range(a + 1, b + 1):
    u = d
    v = x
    while v != 0:
        u, v = v, u % v
    d = u

print(d)

Exemplu de urmărire:

[6,10] → CMMDC(6,7,8,9,10)=1

7. CMMDC al elementelor unei secvențe

Dificil

Enunț

Se citește n, apoi n numere naturale nenule. Determinați CMMDC-ul tuturor numerelor.

Rezolvare

Ideea: Actualizăm CMMDC-ul după fiecare număr citit.

Pașii algoritmului

Citim primul număr ca d.
Pentru fiecare număr următor aplicăm Euclid.
La final afișăm d.

n = int(input())
d = int(input())

for i in range(1, n):
    x = int(input())
    a = d
    b = x
    while b != 0:
        a, b = b, a % b
    d = a

print(d)

Exemplu de urmărire:

4 numere: 24,36,60,84 → CMMDC=12

8. CMMDC și reducerea unei fracții

Dificil

Enunț

Se citesc numărătorul a și numitorul b, cu b > 0. Reduceți fracția la forma ireductibilă.

Rezolvare

Ideea: Împărțim numărătorul și numitorul la CMMDC.

Pașii algoritmului

Calculăm d=CMMDC(a,b).
Numărătorul devine a//d.
Numitorul devine b//d.
Afișăm.

a = int(input())
b = int(input())

x = a
y = b
while y != 0:
    x, y = y, x % y

print(a // x, b // x)

Exemplu de urmărire:

84/126 → d=42 → 2/3

9. CMMDC al două intervale

Dificil

Enunț

Se citesc a,b,c,d cu a<=b și c<=d. Calculați CMMDC-ul tuturor numerelor din cele două intervale reunite.

Rezolvare

Ideea: Procesăm pe rând toate numerele și actualizăm un CMMDC global.

Pașii algoritmului

Pornim cu primul număr.
Aplicăm Euclid cu fiecare număr din primul interval și apoi din al doilea.
Afișăm.

a = int(input())
b = int(input())
c = int(input())
d = int(input())

g = a

for x in range(a + 1, b + 1):
    u, v = g, x
    while v != 0:
        u, v = v, u % v
    g = u

for x in range(c, d + 1):
    u, v = g, x
    while v != 0:
        u, v = v, u % v
    g = u

print(g)

Exemplu de urmărire:

[8,12] și [20,24] → CMMDC=1

10. CMMDC al cifrelor unui număr

Dificil

Enunț

Se citește un număr natural n. Determinați CMMDC-ul tuturor cifrelor lui n.

Rezolvare

Ideea: Pornim cu prima cifră și calculăm succesiv CMMDC cu fiecare cifră.

Pașii algoritmului

Extragem o cifră inițială.
Pentru fiecare cifră următoare aplicăm Euclid.
Dacă CMMDC devine 1, putem ști că nu mai poate scădea.

n = int(input())

g = n % 10
n //= 10

while n > 0:
    c = n % 10
    a = g
    b = c
    while b != 0:
        a, b = b, a % b
    g = a
    n //= 10

print(g)

Exemplu de urmărire:

n=246824 → CMMDC al cifrelor este 2

11. CMMDC al numerelor formate din primele k cifre

Dificil

Enunț

Se citesc n și k, apoi n numere naturale. Calculați CMMDC-ul primelor k numere.

Rezolvare

Ideea: Citim toate valorile, dar actualizăm algoritmul doar pentru primele k.

Pașii algoritmului

Citim k.
Pornim cu primul număr.
Aplicăm Euclid pentru următoarele k-1 valori.

n = int(input())
k = int(input())

g = int(input())

for i in range(1, n):
    x = int(input())
    if i < k:
        a, b = g, x
        while b != 0:
            a, b = b, a % b
        g = a

print(g)

Exemplu de urmărire:

n=5,k=3, valori 18 24 30 49 77 → CMMDC primelor 3=6

12. Verificare dacă două numere au exact un divizor comun

Dificil

Enunț

Se citesc a și b. Verificați dacă singurul lor divizor pozitiv comun este 1.

Rezolvare

Ideea: Acest lucru este echivalent cu CMMDC(a,b)=1.

Pașii algoritmului

Calculăm CMMDC.
Comparăm cu 1.

a = int(input())
b = int(input())

while b != 0:
    a, b = b, a % b

print("DA" if a == 1 else "NU")

Exemplu de urmărire:

8 și 15 → DA

13. Cel mai mare divizor comun care este impar

Dificil

Enunț

Se citesc a și b. Determinați cel mai mare divizor comun impar al lor.

Rezolvare

Ideea: CMMDC-ul obișnuit poate conține factori de 2; îl împărțim repetat la 2.

Pașii algoritmului

Calculăm g=CMMDC(a,b).
Cât timp g este par, îl împărțim la 2.
Rezultatul este partea impară a CMMDC-ului.

a = int(input())
b = int(input())

while b != 0:
    a, b = b, a % b

g = a
while g % 2 == 0:
    g //= 2

print(g)

Exemplu de urmărire:

48 și 72 → CMMDC=24 → partea impară=3

14. CMMDC după eliminarea factorilor de 2

Dificil

Enunț

Se citesc a și b. Eliminați toți factorii 2 din fiecare număr, apoi calculați CMMDC-ul numerelor rămase.

Rezolvare

Ideea: Mai întâi facem numerele impare prin împărțiri repetate la 2, apoi folosim Euclid.

Pașii algoritmului

Împărțim a cât timp este par.
Împărțim b cât timp este par.
Calculăm CMMDC.

a = int(input())
b = int(input())

while a % 2 == 0:
    a //= 2
while b % 2 == 0:
    b //= 2

while b != 0:
    a, b = b, a % b

print(a)

Exemplu de urmărire:

40 și 24 → 5 și 3 → CMMDC=1

15. CMMDC și diferența minimă

Dificil

Enunț

Se citesc a și b. Calculați CMMDC(a,b) și diferența minimă dintre două numere de forma a*k și b*k care sunt egale pentru cel mai mic k pozitiv.

Rezolvare

Ideea: Prima valoare comună pozitivă este CMMMC(a,b), iar diferența cerută este 0; exercițiul verifică legătura dintre multipli comuni.

Pașii algoritmului

Calculăm CMMDC.
Determinăm CMMMC prin formula a*b/g.
Verificăm că este multiplu al ambelor.

a = int(input())
b = int(input())

x, y = a, b
while y != 0:
    x, y = y, x % y

cmmmc = a * b // x
print(x, cmmmc, 0)

Exemplu de urmărire:

6 și 8 → CMMDC=2, CMMMC=24, diferența=0

16. Numărul de perechi cu CMMDC 1

Dificil

Enunț

Se citește n. Determinați câte perechi (a,b), 1<=a<b<=n, sunt prime între ele.

Rezolvare

Ideea: Pentru fiecare pereche calculăm CMMDC prin Euclid.

Pașii algoritmului

Generăm toate perechile.
Calculăm CMMDC.
Numărăm perechile cu rezultat 1.

n = int(input())
cnt = 0

for a in range(1, n):
    for b in range(a + 1, n + 1):
        x, y = a, b
        while y != 0:
            x, y = y, x % y
        if x == 1:
            cnt += 1

print(cnt)

Exemplu de urmărire:

n=5 → perechi coprime: 7

17. CMMDC pentru două numere negative

Dificil

Enunț

Se citesc două numere întregi nenule, care pot fi negative. Determinați CMMDC-ul valorilor lor absolute.

Rezolvare

Ideea: Algoritmul lui Euclid este aplicat pe valorile pozitive.

Pașii algoritmului

Dacă un număr este negativ, îi schimbăm semnul.
Aplicăm Euclid.
Afișăm rezultatul.

a = int(input())
b = int(input())

if a < 0:
    a = -a
if b < 0:
    b = -b

while b != 0:
    a, b = b, a % b

print(a)

Exemplu de urmărire:

−48 și 18 → 6

18. CMMDC al numerelor consecutive dintr-un interval

Dificil

Enunț

Se citește n. Pentru fiecare pereche consecutivă (k,k+1), 1<=k<n, afișați CMMDC-ul și verificați observația rezultată.

Rezolvare

Ideea: Două numere consecutive sunt întotdeauna prime între ele.

Pașii algoritmului

Parcurgem k.
Aplicăm Euclid lui k și k+1.
Afișăm rezultatul.

n = int(input())

for k in range(1, n):
    a, b = k, k + 1
    while b != 0:
        a, b = b, a % b
    print(k, k + 1, a)

Exemplu de urmărire:

Pentru orice k, rezultatul este 1

19. CMMDC și numărul de divizori comuni

Dificil

Enunț

Se citesc a și b. Determinați CMMDC-ul și numărul divizorilor comuni ai lui a și b.

Rezolvare

Ideea: Divizorii comuni ai lui a și b sunt exact divizorii CMMDC(a,b).

Pașii algoritmului

Calculăm g.
Parcurgem divizorii lui g.
Numărăm.

a = int(input())
b = int(input())

while b != 0:
    a, b = b, a % b

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

print(g, cnt)

Exemplu de urmărire:

18 și 24 → g=6; divizori comuni 1,2,3,6 → 4

20. CMMDC și descompunerea comună

Dificil

Enunț

Se citesc a și b. Determinați CMMDC-ul lor și verificați de câte ori îl conține fiecare număr.

Rezolvare

Ideea: După CMMDC, coeficienții a/g și b/g arată părțile rămase după eliminarea factorilor comuni.

Pașii algoritmului

Calculăm g.
Calculăm a//g și b//g.
Afișăm cele trei valori.

a = int(input())
b = int(input())

x, y = a, b
while y != 0:
    x, y = y, x % y

print(x, a // x, b // x)

Exemplu de urmărire:

84 și 126 → 42, 2, 3

5. Descompunerea în factori primi

Descompunerea în factori primi exprimă un număr mai mare decât 1 ca produs de numere prime. Ea stă la baza unor probleme despre numărul de divizori, pătrate perfecte și proprietăți ale factorilor.

Tehnica descompunerii

d = 2
while n > 1:
    while n % d == 0:
        # d este factor prim
        n //= d
    d += 1

Dacă d divide numărul, eliminăm toate aparițiile lui d. Astfel obținem exponentul factorului în descompunere.

1. Descompunerea în factori primi

Dificil

Enunț

Se citește n > 1. Afișați factorii primi ai lui n, cu repetiție.

Rezolvare

Ideea: Încercăm succesiv divizorii începând cu 2 și împărțim cât timp divizorul divide numărul.

Pașii algoritmului

Pornim d=2.
Cât timp d divide n, afișăm d și împărțim n la d.
Trecem la următorul d.
Dacă rămâne n>1, acesta este ultimul factor prim.

n = int(input())
d = 2

while n > 1:
    while n % d == 0:
        print(d, end=" ")
        n //= d
    d += 1

Exemplu de urmărire:

360 → 2 2 2 3 3 5

2. Numărul factorilor primi cu repetiție

Dificil

Enunț

Se citește n > 1. Determinați câți factori primi apar în descompunerea lui n, cu repetiție.

Rezolvare

Ideea: Numărăm de câte ori efectuăm împărțirea exactă.

Pașii algoritmului

Parcurgem divizorii.
La fiecare împărțire exactă incrementăm contorul.
Afișăm contorul.

n = int(input())
d = 2
cnt = 0

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

print(cnt)

Exemplu de urmărire:

360 → 2+2+2+3+3+5 → 6 factori

3. Numărul factorilor primi distincți

Dificil

Enunț

Se citește n > 1. Determinați câți factori primi distincți are n.

Rezolvare

Ideea: Când un divizor d apare cel puțin o dată, numărăm o singură dată acel factor.

Pașii algoritmului

Pentru fiecare d verificăm dacă divide n.
Dacă da, incrementăm și eliminăm toate aparițiile lui d.
Continuăm.

n = int(input())
d = 2
cnt = 0

while n > 1:
    if n % d == 0:
        cnt += 1
        while n % d == 0:
            n //= d
    d += 1

print(cnt)

Exemplu de urmărire:

360 = 2^3*3^2*5 → 3 factori distincți

4. Cel mai mare factor prim

Dificil

Enunț

Se citește n > 1. Determinați cel mai mare factor prim al lui n.

Rezolvare

Ideea: Factorii sunt încercați în ordine crescătoare; ultimul factor găsit este cel mai mare.

Pașii algoritmului

Parcurgem divizorii.
De fiecare dată când d divide n, actualizăm ultimul factor.
Eliminăm toate aparițiile lui d.

n = int(input())
d = 2
ultim = 1

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

print(ultim)

Exemplu de urmărire:

840 → cel mai mare factor prim 7

5. Cel mai mic factor prim

Dificil

Enunț

Se citește n > 1. Determinați cel mai mic factor prim al lui n.

Rezolvare

Ideea: Primul divizor mai mare sau egal cu 2 este automat prim.

Pașii algoritmului

Pornim d=2.
Creștem d până când divide n.
Afișăm d.

n = int(input())
d = 2

while n % d != 0:
    d += 1

print(d)

Exemplu de urmărire:

91 → 7

6. Exponentul lui 2 în descompunere

Dificil

Enunț

Se citește n > 0. Determinați de câte ori apare factorul 2 în descompunerea lui n.

Rezolvare

Ideea: Împărțim repetat la 2 cât timp n este par.

Pașii algoritmului

Inițial exponentul este 0.
Cât timp n%2==0, incrementăm și împărțim.
Afișăm.

n = int(input())
cnt = 0

while n % 2 == 0:
    cnt += 1
    n //= 2

print(cnt)

Exemplu de urmărire:

n=96 → 96=2^5*3 → exponent 5

7. Exponentul unui factor p

Dificil

Enunț

Se citesc n > 0 și un număr prim p. Determinați exponentul lui p în descompunerea lui n.

Rezolvare

Ideea: Împărțim repetat la p.

Pașii algoritmului

Inițial exponent 0.
Cât timp p divide n, incrementăm și împărțim.
Afișăm exponentul.

n = int(input())
p = int(input())
cnt = 0

while n % p == 0:
    cnt += 1
    n //= p

print(cnt)

Exemplu de urmărire:

n=540,p=3 → exponent 3

8. Verificare putere a unui prim

Dificil

Enunț

Se citesc n > 1 și p prim. Verificați dacă n este o putere a lui p, adică n=p^k pentru un k>=1.

Rezolvare

Ideea: Împărțim repetat n la p. Dacă la final rămâne 1, toate factorii au fost p.

Pașii algoritmului

Cât timp n este divizibil cu p, îl împărțim.
Dacă rezultatul final este 1, răspunsul este DA.
Altfel NU.

n = int(input())
p = int(input())

while n % p == 0:
    n //= p

print("DA" if n == 1 else "NU")

Exemplu de urmărire:

81 și 3 → 81→27→9→3→1 → DA

9. Numărul de divizori din descompunerea în factori primi

Dificil

Enunț

Se citește n > 1. Determinați numărul total de divizori pozitivi ai lui n folosind descompunerea în factori primi.

Rezolvare

Ideea: Dacă n=p1^a1*...*pk^ak, numărul divizorilor este (a1+1)...(ak+1).

Pașii algoritmului

Determinăm exponentul fiecărui factor.
Pentru fiecare factor înmulțim rezultatul cu exponent+1.
Afișăm.

n = int(input())
d = 2
numar_divizori = 1

while n > 1:
    exponent = 0
    while n % d == 0:
        exponent += 1
        n //= d
    if exponent > 0:
        numar_divizori *= exponent + 1
    d += 1

print(numar_divizori)

Exemplu de urmărire:

360=2^3*3^2*5 → (3+1)(2+1)(1+1)=24

10. Suma divizorilor folosind factorii primi

Dificil

Enunț

Se citește n > 1. Calculați suma tuturor divizorilor pozitivi folosind descompunerea în factori primi.

Rezolvare

Ideea: Pentru fiecare p^a, contribuția este 1+p+...+p^a; produsul contribuțiilor dă suma tuturor divizorilor.

Pașii algoritmului

Descompunem n.
Pentru fiecare factor calculăm suma puterilor sale.
Înmulțim contribuțiile.

n = int(input())
d = 2
suma = 1

while n > 1:
    p = 1
    termen = 1

    while n % d == 0:
        n //= d
        termen *= d
        p += termen

    if p > 1:
        suma *= p

    d += 1

print(suma)

Exemplu de urmărire:

12=2^2*3 → (1+2+4)(1+3)=28

11. Numărul este pătrat perfect prin factorizare

Dificil

Enunț

Se citește n > 1. Verificați dacă n este pătrat perfect folosind exponenții factorilor primi.

Rezolvare

Ideea: Un număr este pătrat perfect dacă toți exponenții din descompunerea sa sunt pari.

Pașii algoritmului

Descompunem n.
Pentru fiecare factor numărăm exponentul.
Dacă unul este impar, n nu este pătrat perfect.

n = int(input())
d = 2
ok = True

while n > 1:
    exponent = 0
    while n % d == 0:
        exponent += 1
        n //= d
    if exponent % 2 == 1:
        ok = False
    d += 1

print("DA" if ok else "NU")

Exemplu de urmărire:

144=2^4*3^2 → ambii exponenți pari → DA

12. Numărul este cub perfect prin factorizare

Dificil

Enunț

Se citește n > 1. Verificați dacă n este cub perfect folosind exponenții factorilor primi.

Rezolvare

Ideea: Toți exponenții trebuie să fie multipli de 3.

Pașii algoritmului

Descompunem n.
Calculăm fiecare exponent.
Verificăm exponent % 3 == 0.

n = int(input())
d = 2
ok = True

while n > 1:
    exponent = 0
    while n % d == 0:
        exponent += 1
        n //= d
    if exponent % 3 != 0:
        ok = False
    d += 1

print("DA" if ok else "NU")

Exemplu de urmărire:

216=2^3*3^3 → DA

13. Radicalul întreg prin factorizare

Dificil

Enunț

Se citește un pătrat perfect n. Determinați rădăcina pătrată folosind descompunerea în factori primi.

Rezolvare

Ideea: Pentru fiecare exponent par, rădăcina conține factorul cu exponentul înjumătățit.

Pașii algoritmului

Descompunem n.
Pentru fiecare factor p^a, înmulțim rezultatul cu p^(a/2).
Afișăm rezultatul.

n = int(input())
d = 2
rezultat = 1

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

    rezultat *= d ** (exponent // 2)
    d += 1

print(rezultat)

Exemplu de urmărire:

360 nu este pătrat perfect; pentru 144 → 12

14. Numărul factorilor primi impari cu repetiție

Dificil

Enunț

Se citește n > 1. Determinați câți factori primi impari apar în descompunerea lui n, cu repetiție.

Rezolvare

Ideea: Ignorăm factorul 2 și numărăm toate celelalte împărțiri exacte.

Pașii algoritmului

Eliminăm factorii 2.
Parcurgem ceilalți factori.
Numărăm fiecare apariție.

n = int(input())
cnt = 0

while n % 2 == 0:
    n //= 2

d = 3
while n > 1:
    while n % d == 0:
        cnt += 1
        n //= d
    d += 2

print(cnt)

Exemplu de urmărire:

n=360 → factori impari 3,3,5 → 3

15. Produsul factorilor primi distincți

Dificil

Enunț

Se citește n > 1. Calculați produsul factorilor primi distincți ai lui n.

Rezolvare

Ideea: Pentru fiecare factor prim găsit o singură dată, îl înmulțim în rezultat.

Pașii algoritmului

Când d divide n, înmulțim rezultatul cu d.
Eliminăm toate aparițiile lui d.
Continuăm.

n = int(input())
d = 2
produs = 1

while n > 1:
    if n % d == 0:
        produs *= d
        while n % d == 0:
            n //= d
    d += 1

print(produs)

Exemplu de urmărire:

360 → 2*3*5=30

16. Factorul prim cu exponent maxim

Dificil

Enunț

Se citește n > 1. Determinați factorul prim care apare de cele mai multe ori. La egalitate, alegeți factorul mai mare.

Rezolvare

Ideea: Calculăm exponentul fiecărui factor și păstrăm cel mai bun.

Pașii algoritmului

Pentru fiecare d calculăm exponentul.
Comparăm exponentul cu maximul.
La egalitate alegem d mai mare.

n = int(input())
d = 2
max_exp = -1
raspuns = -1

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

    if exponent > max_exp or (exponent == max_exp and d > raspuns):
        if exponent > 0:
            max_exp = exponent
            raspuns = d

    d += 1

print(raspuns, max_exp)

Exemplu de urmărire:

360=2^3*3^2*5 → 2, exponent 3

17. Numărul are exact trei factori primi distincți

Dificil

Enunț

Se citește n > 1. Verificați dacă descompunerea lui n are exact trei factori primi distincți.

Rezolvare

Ideea: Numărăm factorii pentru care exponentul este nenul.

Pașii algoritmului

Descompunem n.
La fiecare factor nou incrementăm contorul.
Comparăm cu 3.

n = int(input())
d = 2
cnt = 0

while n > 1:
    if n % d == 0:
        cnt += 1
        while n % d == 0:
            n //= d
    d += 1

print("DA" if cnt == 3 else "NU")

Exemplu de urmărire:

60=2^2*3*5 → 3 factori distincți → DA

18. Descompunerea și reconstruirea numărului

Dificil

Enunț

Se citește n > 1. Determinați dacă produsul factorilor primi afișați cu repetiție este egal cu n. Afișați produsul reconstruit.

Rezolvare

Ideea: Înmulțim fiecare factor prim găsit în aceeași ordine în care îl extragem.

Pașii algoritmului

Salvăm originalul.
Descompunem și înmulțim factorii în produs.
Comparăm produsul cu originalul.

n = int(input())
original = n
d = 2
produs = 1

while n > 1:
    while n % d == 0:
        produs *= d
        n //= d
    d += 1

print(produs)
print("DA" if produs == original else "NU")

Exemplu de urmărire:

n=420 → produsul factorilor =420 → DA

19. Cel mai mare exponent din factorizare

Dificil

Enunț

Se citește n > 1. Determinați cel mai mare exponent al unui factor prim din descompunerea lui n.

Rezolvare

Ideea: Pentru fiecare factor prim calculăm exponentul și păstrăm maximul.

Pașii algoritmului

Descompunem n.
Numărăm aparițiile factorului.
Actualizăm exponentul maxim.

n = int(input())
d = 2
max_exp = 0

while n > 1:
    exponent = 0
    while n % d == 0:
        exponent += 1
        n //= d
    if exponent > max_exp:
        max_exp = exponent
    d += 1

print(max_exp)

Exemplu de urmărire:

n=432=2^4*3^3 → exponent maxim 4

20. Verificare număr cu exact doi factori primi distincți

Dificil

Enunț

Se citește n > 1. Verificați dacă n are exact doi factori primi distincți.

Rezolvare

Ideea: Numărăm factorii care apar cel puțin o dată.

Pașii algoritmului

Descompunem n.
Numărăm factorii distincți.
Comparăm cu 2.

n = int(input())
d = 2
cnt = 0

while n > 1:
    if n % d == 0:
        cnt += 1
        while n % d == 0:
            n //= d
    d += 1

print("DA" if cnt == 2 else "NU")

Exemplu de urmărire:

72=2^3*3^2 → exact doi factori distincți → DA

6. Conversii între baze de numerație

O reprezentare în baza b folosește cifrele 0,...,b-1. Conversia spre baza 10 folosește puterile bazei, iar conversia din baza 10 folosește împărțiri succesive și resturile lor.

Regula generală

În baza b, o reprezentare cu cifrele c_k...c₁c₀ are valoarea:

c_k * b**k + ... + c_1 * b + c_0

Pentru conversia din baza 10 în baza b, folosim împărțiri repetate la b; resturile citite de jos în sus sunt cifrele rezultatului.

În exercițiile acestei pagini folosim baze între 2 și 9, astfel încât fiecare cifră poate fi reprezentată printr-o cifră zecimală obișnuită.

1. Din baza 2 în baza 10

Dificil

Enunț

Se citește un număr scris în baza 2, fără zerouri sau spații. Convertiți-l în baza 10.

Rezolvare

Ideea: Procesăm cifrele de la dreapta la stânga și folosim puteri ale lui 2.

Pașii algoritmului

Extragem ultima cifră.
O înmulțim cu puterea curentă a lui 2.
Adăugăm la rezultat.
Creștem puterea și eliminăm cifra.

n = int(input())
putere = 1
rezultat = 0

while n > 0:
    cifra = n % 10
    rezultat += cifra * putere
    putere *= 2
    n //= 10

print(rezultat)

Exemplu de urmărire:

101101₂ → 1+4+8+32=45

2. Din baza 3 în baza 10

Dificil

Enunț

Se citește un număr scris în baza 3. Convertiți-l în baza 10.

Rezolvare

Ideea: În baza 3, fiecare cifră se înmulțește cu o putere a lui 3.

Pașii algoritmului

Pornim puterea de la 1.
Procesăm cifrele de la dreapta.
Adunăm cifra*putere.
Înmulțim puterea cu 3.

n = int(input())
putere = 1
rezultat = 0

while n > 0:
    cifra = n % 10
    rezultat += cifra * putere
    putere *= 3
    n //= 10

print(rezultat)

Exemplu de urmărire:

1021₃ → 1+6+0+27=34

3. Din baza 8 în baza 10

Dificil

Enunț

Se citește un număr scris în baza 8. Convertiți-l în baza 10.

Rezolvare

Ideea: Aplicăm aceeași regulă, folosind puteri ale lui 8.

Pașii algoritmului

Extragem cifrele.
Adunăm cifra înmulțită cu puterea lui 8 corespunzătoare.
Actualizăm puterea.

n = int(input())
putere = 1
rezultat = 0

while n > 0:
    cifra = n % 10
    rezultat += cifra * putere
    putere *= 8
    n //= 10

print(rezultat)

Exemplu de urmărire:

157₈ → 1*64+5*8+7=111

4. Din baza 10 în baza 2

Dificil

Enunț

Se citește un număr natural n. Afișați reprezentarea lui în baza 2 folosind împărțiri repetate la 2.

Rezolvare

Ideea: Resturile împărțirilor succesive sunt cifrele binare, citite în ordine inversă.

Pașii algoritmului

Calculăm n%2.
Împărțim n la 2.
Construim invers resturile într-un număr.
La final inversăm rezultatul numeric.

n = int(input())
inv = 0

while n > 0:
    inv = inv * 10 + n % 2
    n //= 2

rezultat = 0
while inv > 0:
    rezultat = rezultat * 10 + inv % 10
    inv //= 10

print(rezultat)

Exemplu de urmărire:

13 → resturi 1,0,1,1 → 1101₂

5. Din baza 10 în baza 8

Dificil

Enunț

Se citește n. Afișați reprezentarea lui în baza 8 folosind împărțiri repetate la 8.

Rezolvare

Ideea: Resturile împărțirilor la 8 sunt cifrele rezultatului de la dreapta la stânga.

Pașii algoritmului

Extragem n%8.
Împărțim la 8.
Construim resturile invers.
Inversăm rezultatul.

n = int(input())
inv = 0

while n > 0:
    inv = inv * 10 + n % 8
    n //= 8

rezultat = 0
while inv > 0:
    rezultat = rezultat * 10 + inv % 10
    inv //= 10

print(rezultat)

Exemplu de urmărire:

83 → 123₈

6. Din baza 10 în baza 3

Dificil

Enunț

Se citește n. Afișați reprezentarea lui în baza 3.

Rezolvare

Ideea: Folosim împărțiri repetate la 3 și citim resturile invers.

Pașii algoritmului

Calculăm restul modulo 3.
Împărțim la 3.
Repetăm.
Refacem ordinea cifrelor.

n = int(input())
inv = 0

while n > 0:
    inv = inv * 10 + n % 3
    n //= 3

rezultat = 0
while inv > 0:
    rezultat = rezultat * 10 + inv % 10
    inv //= 10

print(rezultat)

Exemplu de urmărire:

28 → 1001₃

7. Verificarea unei reprezentări binare

Dificil

Enunț

Se citește un număr natural n. Verificați dacă toate cifrele lui n sunt 0 sau 1.

Rezolvare

Ideea: Parcurgem cifrele și căutăm o cifră diferită de 0 și 1.

Pașii algoritmului

Extragem fiecare cifră.
Dacă este 2..9, reprezentarea nu este binară.
Afișăm DA/NU.

n = int(input())
ok = True

while n > 0:
    c = n % 10
    if c != 0 and c != 1:
        ok = False
    n //= 10

print("DA" if ok else "NU")

Exemplu de urmărire:

101101 → DA; 10201 → NU

8. Valoarea unei cifre într-o bază

Dificil

Enunț

Se citesc n, b și k. Numărul n este reprezentarea unui număr în baza b. Determinați cifra de pe poziția k, numerotând de la dreapta cu 0.

Rezolvare

Ideea: După k împărțiri la b, ultima cifră a rezultatului este cifra cerută.

Pașii algoritmului

Repetăm k ori împărțirea lui n la b.
Afișăm n%b.
Presupunem că n este o reprezentare validă.

n = int(input())
b = int(input())
k = int(input())

for i in range(k):
    n //= b

print(n % b)

Exemplu de urmărire:

n=12021 în baza 3, k=2 → cifra este 0

9. Numărul de cifre în baza 2

Dificil

Enunț

Se citește n > 0. Determinați câte cifre are reprezentarea lui n în baza 2.

Rezolvare

Ideea: Fiecare împărțire la 2 elimină o cifră binară.

Pașii algoritmului

Inițializăm contorul.
Împărțim n la 2 până la 0.
Numărăm împărțirile.

n = int(input())
cnt = 0

while n > 0:
    cnt += 1
    n //= 2

print(cnt)

Exemplu de urmărire:

n=13 → 1101 → 4 cifre

10. Suma cifrelor reprezentării binare

Dificil

Enunț

Se citește n. Calculați suma cifrelor reprezentării sale în baza 2.

Rezolvare

Ideea: Suma cifrelor binare este chiar numărul de biți egali cu 1.

Pașii algoritmului

Extragem n%2.
Adunăm restul.
Împărțim la 2.

n = int(input())
s = 0

while n > 0:
    s += n % 2
    n //= 2

print(s)

Exemplu de urmărire:

13=1101₂ → suma cifrelor = 3

11. Verificarea unei puteri a lui 2 prin baza 2

Dificil

Enunț

Se citește n > 0. Verificați dacă reprezentarea binară a lui n conține exact o cifră 1.

Rezolvare

Ideea: O reprezentare binară cu exact un 1 corespunde unei puteri a lui 2.

Pașii algoritmului

Parcurgem cifrele binare.
Numărăm câte resturi 1 apar.
Verificăm dacă sunt exact 1.

n = int(input())
cnt = 0

while n > 0:
    cnt += n % 2
    n //= 2

print("DA" if cnt == 1 else "NU")

Exemplu de urmărire:

16=10000₂ → exact un 1 → DA

12. Conversie din baza 5 în baza 10 cu Horner

Dificil

Enunț

Se citește o reprezentare n în baza 5. Convertiți-o în baza 10 folosind metoda Horner.

Rezolvare

Ideea: Construim valoarea de la stânga la dreapta: rezultat = rezultat*baza + cifra.

Pașii algoritmului

Determinăm câte cifre are reprezentarea.
Procesăm cifrele de la stânga la dreapta folosind o putere sau o parcurgere inversă.
Actualizăm rezultatul cu formula Horner.

n = int(input())

# Construim mai întâi numărul cu cifrele în ordine inversă.
inv = 0
x = n
while x > 0:
    inv = inv * 10 + x % 10
    x //= 10

rezultat = 0
while inv > 0:
    cifra = inv % 10
    rezultat = rezultat * 5 + cifra
    inv //= 10

print(rezultat)

Exemplu de urmărire:

1324₅ → (((1*5+3)*5+2)*5+4)=214

13. Conversie din baza 10 în baza 5

Dificil

Enunț

Se citește n. Afișați reprezentarea lui în baza 5.

Rezolvare

Ideea: Aplicăm împărțiri succesive la 5.

Pașii algoritmului

Calculăm resturile.
Construim resturile invers.
Le inversăm.

n = int(input())
inv = 0

while n > 0:
    inv = inv * 10 + n % 5
    n //= 5

rezultat = 0
while inv > 0:
    rezultat = rezultat * 10 + inv % 10
    inv //= 10

print(rezultat)

Exemplu de urmărire:

214₁₀ → 1324₅

14. Conversie din baza 10 în baza 7

Dificil

Enunț

Se citește n. Afișați reprezentarea lui în baza 7.

Rezolvare

Ideea: Resturile împărțirilor succesive la 7 formează cifrele rezultatului.

Pașii algoritmului

Împărțim repetat la 7.
Păstrăm resturile.
Le afișăm în ordine inversă.

n = int(input())
inv = 0

while n > 0:
    inv = inv * 10 + n % 7
    n //= 7

rezultat = 0
while inv > 0:
    rezultat = rezultat * 10 + inv % 10
    inv //= 10

print(rezultat)

Exemplu de urmărire:

100₁₀ → 202₇

15. Conversie între două baze, prin baza 10

Dificil

Enunț

Se citesc n, b1 și b2. n este reprezentarea unui număr în baza b1. Convertiți-l în baza b2. Se presupune că b1 și b2 sunt între 2 și 9.

Rezolvare

Ideea: Facem două etape: b1→10 și 10→b2.

Pașii algoritmului

Calculăm valoarea zecimală folosind Horner.
Calculăm resturile prin împărțiri la b2.
Reconstruim reprezentarea.

n = int(input())
b1 = int(input())
b2 = int(input())

inv = 0
x = n
while x > 0:
    inv = inv * 10 + x % 10
    x //= 10

z = 0
while inv > 0:
    z = z * b1 + inv % 10
    inv //= 10

inv = 0
while z > 0:
    inv = inv * 10 + z % b2
    z //= b2

rezultat = 0
while inv > 0:
    rezultat = rezultat * 10 + inv % 10
    inv //= 10

print(rezultat)

Exemplu de urmărire:

1011₂ → 11₁₀ → 23₅

16. Adunarea a două numere binare

Dificil

Enunț

Se citesc două numere reprezentate în baza 2. Calculați suma lor și afișați rezultatul tot în baza 2.

Rezolvare

Ideea: Convertim ambele valori în baza 10, le adunăm, apoi convertim suma în baza 2.

Pașii algoritmului

Convertim primul număr.
Convertim al doilea.
Adunăm valorile zecimale.
Convertim suma în baza 2.

a = int(input())
b = int(input())

def baza2_la10(n):
    p = 1
    s = 0
    while n > 0:
        s += (n % 10) * p
        p *= 2
        n //= 10
    return s

def baza10_la2(n):
    inv = 0
    while n > 0:
        inv = inv * 10 + n % 2
        n //= 2
    r = 0
    while inv > 0:
        r = r * 10 + inv % 10
        inv //= 10
    return r

s = baza2_la10(a) + baza2_la10(b)
print(baza10_la2(s))

Exemplu de urmărire:

1011₂ + 110₂ = 10001₂

17. Verificarea reprezentării în baza b

Dificil

Enunț

Se citesc n și b, cu 2<=b<=9. Verificați dacă toate cifrele lui n sunt mai mici decât b.

Rezolvare

Ideea: O cifră este validă în baza b dacă este între 0 și b-1.

Pașii algoritmului

Extragem fiecare cifră.
Dacă apare o cifră >= b, reprezentarea este invalidă.
Afișăm DA/NU.

n = int(input())
b = int(input())
ok = True

while n > 0:
    c = n % 10
    if c >= b:
        ok = False
    n //= 10

print("DA" if ok else "NU")

Exemplu de urmărire:

n=1234,b=4 → cifra 4 nu este permisă → NU

18. Numărul de cifre 1 într-o reprezentare în baza b

Dificil

Enunț

Se citesc n și b, 2<=b<=9. Determinați de câte ori apare cifra 1 în reprezentarea n în baza b.

Rezolvare

Ideea: Parcurgem cifrele reprezentării, de la dreapta, prin modulo și împărțire la b.

Pașii algoritmului

Extragem n%b.
Comparăm cu 1.
Împărțim n la b.
Continuăm.

n = int(input())
b = int(input())
cnt = 0

while n > 0:
    if n % b == 1:
        cnt += 1
    n //= b

print(cnt)

Exemplu de urmărire:

n=100,b=2 → 1100100₂ → cifra 1 apare 3 ori

19. Restul lui n modulo b fără operatorul %

Dificil

Enunț

Se citesc n și b > 0. Determinați restul împărțirii lui n la b folosind doar //, *, + și -.

Rezolvare

Ideea: Restul este n - (n//b)*b.

Pașii algoritmului

Calculăm câtul n//b.
Înmulțim câtul cu b.
Scădem din n.

n = int(input())
b = int(input())

rest = n - (n // b) * b
print(rest)

Exemplu de urmărire:

29 și 6 → 29-(4*6)=5

20. Conversie 10→2 fără construirea inversului ca număr

Dificil

Enunț

Se citește n. Afișați reprezentarea binară folosind recursivitatea nu este permisă; folosiți doar bucle și construiți rezultatul cu puteri ale lui 2.

Rezolvare

Ideea: Mai întâi găsim cea mai mare putere a lui 2 care nu depășește n, apoi decidem fiecare bit.

Pașii algoritmului

Găsim cea mai mare putere a lui 2 <= n.
Pentru fiecare putere verificăm dacă poate fi scăzută din n.
Afișăm 1 sau 0 și actualizăm n.
Înjumătățim puterea la fiecare pas.

n = int(input())

p = 1
while p * 2 <= n:
    p *= 2

while p > 0:
    if n >= p:
        print(1, end="")
        n -= p
    else:
        print(0, end="")
    p //= 2

Exemplu de urmărire:

n=13 → p=8 → biții 1 1 0 1 → 1101

🔁 Recapitulare finală

Capitol	Ce trebuie să poți face
Prelucrarea numerelor	să construiești, transformi, inversezi și verifici proprietăți ale numerelor
Cifrele	să extragi, numeri, compari și grupezi cifre
Divizori și multipli	să testezi divizibilitatea, să generezi divizori și multipli și să calculezi sume/numărări
CMMDC	să aplici Euclid prin scăderi și prin resturi și să-l folosești în probleme derivate
Factori primi	să descompui numere și să folosești exponenții factorilor pentru alte proprietăți
Baze de numerație	să convertești între baza 10 și alte baze și între două baze prin baza 10

Checklist: înainte de a scrie codul, identifică exact ce trebuie parcurs, ce informație trebuie păstrată și când se modifică variabilele. După cod, urmărește manual cel puțin un exemplu.