Sari la conținut
EduCamp

Tematică științifică · 1.5

Algoritmi elementari

Prelucrarea cifrelor unui număr, divizibilitatea și divizorii, testarea primalității, algoritmul lui Euclid, descompunerea în factori primi, prelucrarea secvențelor de valori și generarea șirurilor recurente, scrise în pseudocod, în C++ și în Python.

Algoritmii elementari sunt cei pe care se bazează rezolvarea problemelor:

  • probleme cu numere și cu cifrele numerelor;
  • probleme de divizibilitate;
  • prelucrarea unor secvențe de valori;
  • generarea șirurilor recurente.

Aceștia se cer la examen scriși ca subprogram, cu antetul dat în enunț: subprogramul primește un număr sau o secvență și întoarce un rezultat, iar restul rezolvării îl apelează. De aceea algoritmii de mai jos sunt scriși în aceeași formă, în pseudocod și în cele două limbaje. La sfârșitul fiecărei secțiuni, programul principal arată cum se apelează subprogramele.

Prelucrarea cifrelor unui număr

Toate prelucrările cifrelor se bazează pe două operații. Restul împărțirii la 10 este ultima cifră a numărului, cea mai puțin semnificativă. Câtul împărțirii întregi la 10 este numărul rămas după eliminarea acestei cifre.

cât timp n ≠ 0 execută
    c ← n % 10          { se extrage cifra curentă, de la dreapta spre stânga }
    { se prelucrează cifra c }
    n ← [n / 10]        { se elimină cifra prelucrată }
sfcât timp

Structura rămâne aceeași de la o problemă la alta; se schimbă numai prelucrarea cifrei.

ProblemaPrelucrarea cifrei
suma cifrelors ← s + c
produsul cifrelorp ← p * c
produsul cifrelor prime imparedacă c = 3 sau c = 5 sau c = 7 atunci p ← p * c
numărul de cifrenr ← nr + 1
cifra maximădacă c > maxim atunci maxim ← c, cu maxim ← 0 la început
cifra minimădacă c < minim atunci minim ← c, cu minim ← 9 la început
numărul aparițiilor cifrei kdacă c = k atunci nr ← nr + 1
numărul cifrelor paredacă c % 2 = 0 atunci nr ← nr + 1
răsturnatul număruluirasturnat ← rasturnat * 10 + c

Suma cifrelor este cel mai cerut subprogram al acestui subcapitol.

Algoritm

sumaCifrelor(n):
    s ← 0
    cât timp n ≠ 0 execută
        s ← s + n % 10
        n ← [n / 10]
    sfcât timp
    returnează s

C++

int sumaCifrelor(int n) {
    int s = 0;
    while (n != 0) {
        s = s + n % 10;
        n = n / 10;
    }
    return s;
}

Python

def suma_cifrelor(n):
    s = 0
    while n != 0:
        s = s + n % 10
        n = n // 10
    return s

Algoritm

rasturnat(n):
    r ← 0
    cât timp n ≠ 0 execută
        r ← r * 10 + n % 10
        n ← [n / 10]
    sfcât timp
    returnează r

C++

int rasturnat(int n) {
    int r = 0;
    while (n != 0) {
        r = r * 10 + n % 10;
        n = n / 10;
    }
    return r;
}

Python

def rasturnat(n):
    r = 0
    while n != 0:
        r = r * 10 + n % 10
        n = n // 10
    return r

Pentru 8997899 se obține pe rând 59, apoi 14, apoi 5.

Algoritm

cifraDeControl(n):
    cât timp n > 9 execută
        n ← sumaCifrelor(n)
    sfcât timp
    returnează n

C++

int cifraDeControl(int n) {
    while (n > 9)
        n = sumaCifrelor(n);
    return n;
}

Python

def cifra_de_control(n):
    while n > 9:
        n = suma_cifrelor(n)
    return n

Cifrele distincte nu se pot verifica cu răsturnatul. Se folosește un vector de frecvență cu zece poziții, în care se numără aparițiile fiecărei cifre.

Algoritm

cifreDistincte(n):
    f ← vector de 10 zerouri
    cât timp n ≠ 0 execută
        c ← n % 10
        f[c] ← f[c] + 1
        dacă f[c] > 1 atunci
            returnează fals
        sfdacă
        n ← [n / 10]
    sfcât timp
    returnează adevărat

C++

bool cifreDistincte(int n) {
    int frecventa[10] = {0};
    while (n != 0) {
        int c = n % 10;
        frecventa[c]++;
        if (frecventa[c] > 1)
            return false;
        n = n / 10;
    }
    return true;
}

Python

def cifre_distincte(n):
    frecventa = [0] * 10
    while n != 0:
        c = n % 10
        frecventa[c] += 1
        if frecventa[c] > 1:
            return False
        n = n // 10
    return True

Numărul cifrelor distincte se obține din același vector de frecvență: se numără cifrele care apar pentru prima dată. Pentru n = 2638311 se obțin 5 cifre distincte: 1, 2, 3, 6 și 8.

Algoritm

nrCifreDistincte(n):
    f ← vector de 10 zerouri
    nr ← 0
    repetă
        c ← n % 10
        dacă f[c] = 0 atunci
            nr ← nr + 1
        sfdacă
        f[c] ← 1
        n ← [n / 10]
    până când n = 0
    returnează nr

C++

int nrCifreDistincte(int n) {
    int f[10] = {0}, nr = 0;
    do {
        int c = n % 10;
        if (f[c] == 0)
            nr++;
        f[c] = 1;
        n = n / 10;
    } while (n != 0);
    return nr;
}

Python

def nr_cifre_distincte(n):
    f = [0] * 10
    nr = 0
    while True:
        c = n % 10
        if f[c] == 0:
            nr += 1
        f[c] = 1
        n = n // 10
        if n == 0:
            break
    return nr

Structura repetă … până când se execută cel puțin o dată, deci pentru n = 0 se numără cifra 0.

Compunerea unui număr din cifrele sale. Cifrele se citesc pe rând, începând cu cea mai semnificativă. Fiecare cifră nouă se adaugă la dreapta numărului construit până atunci: numărul se înmulțește cu 10, apoi se adună cifra. Citirea se oprește la prima valoare care nu este cifră.

Algoritm

nr ← 0
citește c
cât timp c ≥ 0 și c ≤ 9 execută
    nr ← nr * 10 + c
    citește c
sfcât timp
scrie nr

C++

int nr = 0, c;
cin >> c;
while (c >= 0 && c <= 9) {
    nr = nr * 10 + c;
    cin >> c;
}
cout << nr;

Python

nr = 0
c = int(input())
while 0 <= c <= 9:
    nr = nr * 10 + c
    c = int(input())
print(nr)

Pentru un număr scris în baza 2, condiția devine c = 0 sau c = 1. Pentru valorile citite 1, 0, 1, 1, 5 se obține 1011.

Numărul format din anumite cifre ale lui n, în ordinea din n. Cifrele se extrag de la dreapta spre stânga, deci compunerea cu r * 10 + c le-ar așeza în ordine inversă. Fiecare cifră păstrată se înmulțește cu puterea lui 10 corespunzătoare locului ei și se adaugă în fața cifrelor păstrate anterior. Pentru n = 27348 și cifrele pare se obține 248.

Algoritm

cifrePare(n):
    r ← 0; p ← 1
    cât timp n ≠ 0 execută
        c ← n % 10
        dacă c % 2 = 0 atunci
            r ← r + c * p
            p ← p * 10
        sfdacă
        n ← [n / 10]
    sfcât timp
    returnează r

C++

int cifrePare(int n) {
    int r = 0, p = 1;
    while (n != 0) {
        int c = n % 10;
        if (c % 2 == 0) {
            r = r + c * p;
            p = p * 10;
        }
        n = n / 10;
    }
    return r;
}

Python

def cifre_pare(n):
    r = 0
    p = 1
    while n != 0:
        c = n % 10
        if c % 2 == 0:
            r = r + c * p
            p = p * 10
        n = n // 10
    return r

Dacă n nu are nicio cifră pară, subprogramul întoarce 0. Eliminarea unei cifre se face la fel: pentru a elimina toate aparițiile cifrei k, se păstrează cifrele cu c ≠ k.

Inserarea unei cifre folosește aceeași schemă. Cifra inserată se adaugă și ea la rezultat, pe locul următor, iar p se înmulțește încă o dată cu 10. Cifrele se parcurg de la dreapta spre stânga, deci o cifră care trebuie să apară în număr după cifra c se adaugă înaintea lui c. Subprogramul de mai jos inserează cifra k după fiecare cifră pară a lui n: pentru n = 2731 și k = 0 se obține 20731.

Algoritm

insereaza(n, k):
    r ← 0; p ← 1
    cât timp n ≠ 0 execută
        c ← n % 10
        dacă c % 2 = 0 atunci
            r ← r + k * p
            p ← p * 10
        sfdacă
        r ← r + c * p
        p ← p * 10
        n ← [n / 10]
    sfcât timp
    returnează r

C++

long long insereaza(int n, int k) {
    long long r = 0, p = 1;
    while (n != 0) {
        int c = n % 10;
        if (c % 2 == 0) {
            r = r + k * p;
            p = p * 10;
        }
        r = r + c * p;
        p = p * 10;
        n = n / 10;
    }
    return r;
}

Python

def insereaza(n, k):
    r = 0
    p = 1
    while n != 0:
        c = n % 10
        if c % 2 == 0:
            r = r + k * p
            p = p * 10
        r = r + c * p
        p = p * 10
        n = n // 10
    return r

Sortarea cifrelor unui număr se face cu vectorul de frecvență. Se numără aparițiile fiecărei cifre, apoi numărul se compune parcurgând cifrele de la 9 la 0: fiecare cifră se adaugă de atâtea ori de câte ori apare. Se obține cel mai mare număr scris cu aceleași cifre: pentru 30512 se obține 53210.

Algoritm

cifreDescrescator(n):
    f ← vector de 10 zerouri
    cât timp n ≠ 0 execută
        f[n % 10] ← f[n % 10] + 1
        n ← [n / 10]
    sfcât timp
    r ← 0
    pentru c ← 9, 0, -1 execută
        pentru i ← 1, f[c] execută
            r ← r * 10 + c
        sfpentru
    sfpentru
    returnează r

C++

int cifreDescrescator(int n) {
    int f[10] = {0}, r = 0;
    while (n != 0) {
        f[n % 10]++;
        n = n / 10;
    }
    for (int c = 9; c >= 0; c--)
        for (int i = 1; i <= f[c]; i++)
            r = r * 10 + c;
    return r;
}

Python

def cifre_descrescator(n):
    f = [0] * 10
    while n != 0:
        f[n % 10] += 1
        n = n // 10
    r = 0
    for c in range(9, -1, -1):
        for i in range(f[c]):
            r = r * 10 + c
    return r

Numărul format din cifrele a două numere. Cifrele lui b se scriu la dreapta cifrelor lui a: a se înmulțește cu 10 de atâtea ori câte cifre are b, apoi se adună b. În subiectul de Definitivat din 2025, operația este numită „alipire”, de unde și numele subprogramului. Pentru a = 154 și b = 45 se obține 15445. Puterea lui 10 pornește de la 10, nu de la 1, pentru ca b = 0 să fie numărat ca număr de o cifră.

Algoritm

alipire(a, b):
    p ← 10
    t ← [b / 10]
    cât timp t ≠ 0 execută
        p ← p * 10
        t ← [t / 10]
    sfcât timp
    returnează a * p + b

C++

long long alipire(int a, int b) {
    long long p = 10;
    int t = b / 10;
    while (t != 0) {
        p = p * 10;
        t = t / 10;
    }
    return a * p + b;
}

Python

def alipire(a, b):
    p = 10
    t = b // 10
    while t != 0:
        p = p * 10
        t = t // 10
    return a * p + b

Programul principal. Subprogramele se scriu înaintea funcției main, iar în main se citesc datele și se apelează subprogramele. Parametrul n este transmis prin valoare: subprogramul lucrează pe o copie, deci n din programul principal rămâne neschimbat și poate fi folosit la apelurile următoare.

Pseudocod

citește n
scrie sumaCifrelor(n)
scrie rasturnat(n)
dacă n = rasturnat(n) atunci
    scrie "palindrom"
altfel
    scrie "nu este palindrom"
sfdacă
scrie cifraDeControl(n)
dacă cifreDistincte(n) atunci
    scrie "cifre distincte"
altfel
    scrie "cifre care se repetă"
sfdacă
scrie nrCifreDistincte(n)
scrie cifrePare(n)
scrie insereaza(n, 0)
scrie cifreDescrescator(n)
scrie alipire(n, sumaCifrelor(n))

Implementare în C++

#include <iostream>
using namespace std;

// subprogramele din aceasta sectiune,
// scrise ca mai sus

int main() {
    int n;
    cin >> n;

    cout << sumaCifrelor(n) << '\n';
    cout << rasturnat(n) << '\n';
    if (n == rasturnat(n))
        cout << "palindrom\n";
    else
        cout << "nu este palindrom\n";
    cout << cifraDeControl(n) << '\n';
    if (cifreDistincte(n))
        cout << "cifre distincte\n";
    else
        cout << "cifre care se repeta\n";
    cout << nrCifreDistincte(n) << '\n';
    cout << cifrePare(n) << '\n';
    cout << insereaza(n, 0) << '\n';
    cout << cifreDescrescator(n) << '\n';
    cout << alipire(n, sumaCifrelor(n)) << '\n';
    return 0;
}

Implementare în Python

# subprogramele din aceasta sectiune,
# scrise ca mai sus

n = int(input())

print(suma_cifrelor(n))
print(rasturnat(n))
if n == rasturnat(n):
    print("palindrom")
else:
    print("nu este palindrom")
print(cifra_de_control(n))
if cifre_distincte(n):
    print("cifre distincte")
else:
    print("cifre care se repeta")
print(nr_cifre_distincte(n))
print(cifre_pare(n))
print(insereaza(n, 0))
print(cifre_descrescator(n))
print(alipire(n, suma_cifrelor(n)))

În Python, programul principal nu are o funcție anume. Instrucțiunile scrise după definițiile subprogramelor, fără indentare, se execută în ordine.

Pentru n = 12321, programul scrie pe rânduri separate: 9, 12321, palindrom, 9, cifre care se repetă, 3, 22, 1203201, 32211 și 123219.

Divizibilitate și divizori

Generarea divizorilor

Varianta directă încearcă pe rând toate valorile de la 1 la n și efectuează n împărțiri.

Divizorii apar însă în perechi: dacă d este divizor al lui n, atunci și n / d este divizor al lui n. Pentru n = 12 perechile sunt (1, 12), (2, 6) și (3, 4). Din fiecare pereche, cel puțin unul dintre divizori este mai mic sau egal cu rădăcina pătrată a lui n. Se încearcă atunci numai valorile cu d * d ≤ n, iar pentru fiecare divizor găsit se ia în seamă și perechea lui.

Algoritm

divizori(n):
    d ← 1
    cât timp d * d ≤ n execută
        dacă n % d = 0 atunci
            scrie d
            dacă d ≠ [n / d] atunci
                scrie [n / d]
            sfdacă
        sfdacă
        d ← d + 1
    sfcât timp

C++

void divizori(int n) {
    for (int d = 1; d * d <= n; d++)
        if (n % d == 0) {
            cout << d << " ";
            if (d != n / d)
                cout << n / d << " ";
        }
}

Python

def divizori(n):
    d = 1
    while d * d <= n:
        if n % d == 0:
            print(d, end=" ")
            if d != n // d:
                print(n // d, end=" ")
        d += 1

Condiția d ≠ n / d împiedică luarea în seamă de două ori a divizorului din mijloc, la numerele care sunt pătrate perfecte: pentru n = 36, divizorul 6 formează pereche cu el însuși.

Aceeași parcurgere dă numărul divizorilor și suma divizorilor; se schimbă numai ce se face cu divizorul găsit.

Algoritm

numarulDivizorilor(n):
    nr ← 0
    d ← 1
    cât timp d * d ≤ n execută
        dacă n % d = 0 atunci
            nr ← nr + 1
            dacă d ≠ [n / d] atunci
                nr ← nr + 1
            sfdacă
        sfdacă
        d ← d + 1
    sfcât timp
    returnează nr

C++

int numarulDivizorilor(int n) {
    int nr = 0;
    for (int d = 1; d * d <= n; d++)
        if (n % d == 0) {
            nr++;
            if (d != n / d) nr++;
        }
    return nr;
}

Python

def numarul_divizorilor(n):
    nr = 0
    d = 1
    while d * d <= n:
        if n % d == 0:
            nr += 1
            if d != n // d:
                nr += 1
        d += 1
    return nr

Un număr prim nu are divizori proprii.

Algoritm

divizoriProprii(n):
    pentru d ← 2, [n / 2] execută
        dacă n % d = 0 atunci
            scrie d
        sfdacă
    sfpentru

C++

void divizoriProprii(int n) {
    for (int d = 2; d <= n / 2; d++)
        if (n % d == 0)
            cout << d << " ";
}

Python

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

Cel mai mare divizor propriu se obține din cel mai mic: dacă d este cel mai mic divizor al lui n mai mare decât 1, atunci n / d este cel mai mare divizor al lui n mai mic decât n. Pentru 45, cel mai mic divizor este 3, deci cel mai mare divizor propriu este 15. Dacă nu există niciun d cu d * d ≤ n care să-l dividă pe n, atunci n este prim și nu are divizori proprii; subprogramul întoarce 0.

Algoritm

divPropriuMaxim(n):
    d ← 2
    cât timp d * d ≤ n execută
        dacă n % d = 0 atunci
            returnează [n / d]
        sfdacă
        d ← d + 1
    sfcât timp
    returnează 0

C++

int divPropriuMaxim(int n) {
    for (int d = 2; d * d <= n; d++)
        if (n % d == 0)
            return n / d;
    return 0;
}

Python

def div_propriu_maxim(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            return n // d
        d += 1
    return 0

Suma divizorilor strict mai mici decât n se calculează cu aceeași parcurgere: 1 se adună de la început, iar n nu se adună. După această sumă, numerele se împart în trei categorii:

Suma tuturor divizorilor lui n, inclusiv n, este sumaDivMici(n) + n.

Algoritm

sumaDivMici(n):
    dacă n = 1 atunci
        returnează 0
    sfdacă
    s ← 1
    d ← 2
    cât timp d * d ≤ n execută
        dacă n % d = 0 atunci
            s ← s + d
            dacă d ≠ [n / d] atunci
                s ← s + [n / d]
            sfdacă
        sfdacă
        d ← d + 1
    sfcât timp
    returnează s

C++

int sumaDivMici(int n) {
    if (n == 1) return 0;
    int s = 1;
    for (int d = 2; d * d <= n; d++)
        if (n % d == 0) {
            s = s + d;
            if (d != n / d)
                s = s + n / d;
        }
    return s;
}

Python

def suma_div_mici(n):
    if n == 1:
        return 0
    s = 1
    d = 2
    while d * d <= n:
        if n % d == 0:
            s = s + d
            if d != n // d:
                s = s + n // d
        d += 1
    return s

De exemplu, 16 = 4 · 4. Se ia partea întreagă a rădăcinii pătrate din n și se verifică dacă pătratul ei este egal cu n.

Algoritm

patratPerfect(n):
    r ← [√n]
    returnează r * r = n

C++

bool patratPerfect(int n) {
    int r = sqrt(n);
    return r * r == n;
}

Python

import math

def patrat_perfect(n):
    r = math.isqrt(n)
    return r * r == n

Comparația r * r = n se face între numere întregi. Varianta sqrt(n) == (int)sqrt(n) compară numere reale și, la valori mari, de tip long long, poate da un rezultat greșit. În C++, funcția sqrt cere biblioteca <cmath>. În Python, math.isqrt întoarce direct partea întreagă a rădăcinii, calculată fără numere reale.

Testarea primalității

Numerele 0 și 1 nu sunt prime. Testarea se face după criteriul următor: un număr natural n mai mare decât 1 este prim dacă nu are divizori cuprinși între 2 și partea întreagă a rădăcinii pătrate din n. Marginea se justifică la fel ca la generarea divizorilor: un divizor mai mare decât rădăcina pătrată are întotdeauna perechea lui mai mică decât ea, deci ar fi fost deja găsită.

Algoritm

prim(n):
    dacă n < 2 atunci
        returnează fals
    sfdacă
    dacă n % 2 = 0 atunci
        returnează n = 2
    sfdacă
    d ← 3
    cât timp d * d ≤ n execută
        dacă n % d = 0 atunci
            returnează fals
        sfdacă
        d ← d + 2
    sfcât timp
    returnează adevărat

C++

bool prim(int n) {
    if (n < 2) return false;
    if (n % 2 == 0) return n == 2;
    for (int d = 3; d * d <= n; d = d + 2)
        if (n % d == 0) return false;
    return true;
}

Python

def prim(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d += 2
    return True

Condiția se scrie d * d ≤ n, nu d ≤ sqrt(n). Funcția sqrt lucrează cu numere reale și, la pătrate perfecte mari, poate întoarce o valoare cu foarte puțin mai mică decât rădăcina exactă, caz în care ultimul divizor nu mai este verificat.

Algoritmul lui Euclid

Algoritmul determină cel mai mare divizor comun a două numere naturale. Se bazează pe teorema împărțirii cu rest: orice divizor comun al numerelor a și b este divizor și al restului împărțirii lui a la b.

Algoritm

cmmdc(a, b):
    cât timp b ≠ 0 execută
        r ← a % b
        a ← b
        b ← r
    sfcât timp
    returnează a

C++

int cmmdc(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

Python

def cmmdc(a, b):
    while b != 0:
        a, b = b, a % b
    return a

Mulțimea divizorilor comuni nu se schimbă de la un pas la altul, iar restul scade strict, deci algoritmul se încheie după un număr finit de pași.

Varianta cu scăderi se bazează pe faptul că orice divizor comun al numerelor a și b divide și diferența lor. Din numărul mai mare se scade numărul mai mic, până când cele două devin egale.

Algoritm

cmmdcScaderi(a, b):
    cât timp a ≠ b execută
        dacă a > b atunci
            a ← a - b
        altfel
            b ← b - a
        sfdacă
    sfcât timp
    returnează a

C++

int cmmdcScaderi(int a, int b) {
    while (a != b)
        if (a > b)
            a = a - b;
        else
            b = b - a;
    return a;
}

Python

def cmmdc_scaderi(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    return a

Cel mai mic multiplu comun se obține din cel mai mare divizor comun, folosind egalitatea a · b = cmmdc(a, b) · cmmmc(a, b). Împărțirea se face înaintea înmulțirii, ca produsul să nu depășească domeniul tipului.

Algoritm

cmmmc(a, b):
    returnează [a / cmmdc(a, b)] * b

C++

long long cmmmc(int a, int b) {
    return (long long)a / cmmdc(a, b) * b;
}

Python

def cmmmc(a, b):
    return a // cmmdc(a, b) * b

Descompunerea în factori primi

Se încearcă pe rând divizorii începând de la 2. Fiecare divizor găsit se elimină complet din număr, prin împărțiri repetate. Un divizor găsit astfel nu poate fi decât prim, deoarece toți divizorii mai mici au fost deja eliminați.

Algoritm

descompune(n):
    d ← 2
    cât timp d * d ≤ n execută
        dacă n % d = 0 atunci
            p ← 0
            cât timp n % d = 0 execută
                n ← [n / d]
                p ← p + 1
            sfcât timp
            scrie d, "^", p
        sfdacă
        d ← d + 1
    sfcât timp
    dacă n > 1 atunci
        scrie n, "^1"
    sfdacă

C++

void descompune(int n) {
    for (int d = 2; d * d <= n; d++)
        if (n % d == 0) {
            int p = 0;
            while (n % d == 0) {
                n = n / d;
                p++;
            }
            cout << d << "^" << p << " ";
        }
    if (n > 1) cout << n << "^1";
}

Python

def descompune(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            p = 0
            while n % d == 0:
                n = n // d
                p += 1
            print(f"{d}^{p}", end=" ")
        d += 1
    if n > 1:
        print(f"{n}^1", end=" ")

Din schema descompunerii se obțin mai mulți algoritmi; se schimbă numai ce se face cu factorul găsit.

  • Divizorii primi se scriu fără exponenți: pentru 360 se obține 2 3 5.
  • Numărul factorilor primi distincți se obține numărând factorii în loc de a-i scrie: pentru 360 se obține 3. Suma factorilor primi distincți se obține adunându-i: pentru 360 se obține 2 + 3 + 5 = 10.
  • Cel mai mare factor prim este ultimul factor găsit sau, dacă la sfârșit n > 1, valoarea rămasă în n: pentru 360 se obține 5, iar pentru 14 se obține 7.

Algoritm

divizoriPrimi(n):
    d ← 2
    cât timp d * d ≤ n execută
        dacă n % d = 0 atunci
            scrie d
            cât timp n % d = 0 execută
                n ← [n / d]
            sfcât timp
        sfdacă
        d ← d + 1
    sfcât timp
    dacă n > 1 atunci
        scrie n
    sfdacă

nrFactoriPrimi(n):
    nr ← 0
    d ← 2
    cât timp d * d ≤ n execută
        dacă n % d = 0 atunci
            nr ← nr + 1
            cât timp n % d = 0 execută
                n ← [n / d]
            sfcât timp
        sfdacă
        d ← d + 1
    sfcât timp
    dacă n > 1 atunci
        nr ← nr + 1
    sfdacă
    returnează nr

factorPrimMaxim(n):
    maxim ← 1
    d ← 2
    cât timp d * d ≤ n execută
        cât timp n % d = 0 execută
            maxim ← d
            n ← [n / d]
        sfcât timp
        d ← d + 1
    sfcât timp
    dacă n > 1 atunci
        maxim ← n
    sfdacă
    returnează maxim

C++

void divizoriPrimi(int n) {
    for (int d = 2; d * d <= n; d++)
        if (n % d == 0) {
            cout << d << " ";
            while (n % d == 0)
                n = n / d;
        }
    if (n > 1) cout << n;
}

int nrFactoriPrimi(int n) {
    int nr = 0;
    for (int d = 2; d * d <= n; d++)
        if (n % d == 0) {
            nr++;
            while (n % d == 0)
                n = n / d;
        }
    if (n > 1) nr++;
    return nr;
}

int factorPrimMaxim(int n) {
    int maxim = 1;
    for (int d = 2; d * d <= n; d++)
        while (n % d == 0) {
            maxim = d;
            n = n / d;
        }
    if (n > 1) maxim = n;
    return maxim;
}

Python

def divizori_primi(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            print(d, end=" ")
            while n % d == 0:
                n = n // d
        d += 1
    if n > 1:
        print(n, end=" ")

def nr_factori_primi(n):
    nr = 0
    d = 2
    while d * d <= n:
        if n % d == 0:
            nr += 1
            while n % d == 0:
                n = n // d
        d += 1
    if n > 1:
        nr += 1
    return nr

def factor_prim_maxim(n):
    maxim = 1
    d = 2
    while d * d <= n:
        while n % d == 0:
            maxim = d
            n = n // d
        d += 1
    if n > 1:
        maxim = n
    return maxim

Exponentul unui factor prim p în descompunerea lui n este numărul de împărțiri exacte ale lui n la p. Pentru n = 360 și p = 2 se obține 3, fiindcă 360 = 2³ · 3² · 5.

Reconstruirea numărului din descompunere se face înmulțind puterile factorilor. Se citesc k perechi (factor, exponent), iar fiecare putere se calculează prin înmulțiri repetate. Pentru perechile (2, 3), (3, 2), (5, 1) se obține 8 · 9 · 5 = 360.

Algoritm

exponent(n, p):
    e ← 0
    cât timp n % p = 0 execută
        n ← [n / p]
        e ← e + 1
    sfcât timp
    returnează e

putere(b, e):
    r ← 1
    pentru i ← 1, e execută
        r ← r * b
    sfpentru
    returnează r

{ reconstruirea }
citește k
n ← 1
pentru i ← 1, k execută
    citește f, e
    n ← n * putere(f, e)
sfpentru
scrie n

C++

int exponent(int n, int p) {
    int e = 0;
    while (n % p == 0) {
        n = n / p;
        e++;
    }
    return e;
}

long long putere(int b, int e) {
    long long r = 1;
    for (int i = 1; i <= e; i++)
        r = r * b;
    return r;
}

// reconstruirea, in main:
int k, f, e;
long long n = 1;
cin >> k;
for (int i = 1; i <= k; i++) {
    cin >> f >> e;
    n = n * putere(f, e);
}
cout << n;

Python

def exponent(n, p):
    e = 0
    while n % p == 0:
        n = n // p
        e += 1
    return e

def putere(b, e):
    r = 1
    for i in range(e):
        r = r * b
    return r

# reconstruirea:
k = int(input())
n = 1
for i in range(k):
    f, e = map(int, input().split())
    n = n * putere(f, e)
print(n)

Numere definite prin divizori

Mai multe categorii de numere din enunțuri se recunosc cu subprogramele de mai sus.

Un număr are exact 3 divizori dacă și numai dacă este pătratul unui număr prim. Divizorii lui p² sunt 1, p și p². Exemple: 4, 9, 25, 49.

La un număr semiprim, numărând factorii primi împreună cu exponenții lor, se obține exact 2. Exemple: 4 = 2 · 2, 6 = 2 · 3, 15 = 3 · 5.

Materialul acesta se citește pe educamp.ro și nu se tipărește.

Ce cuprinde subcapitolul

  1. Prelucrarea cifrelor unui număr
  2. Divizibilitate și divizori
  3. Numere definite prin proprietăți
  4. Interschimbarea valorilor a două variabile
  5. Prelucrarea unei secvențe de valori
  6. Generarea șirurilor recurente
  7. Puteri, factorial, aranjamente și combinări
  8. Apariții la examen

Continuă lectura ca și cursant

Cel puțin un subcapitol din fiecare capitol este disponibil gratuit și integral. Pentru a citi toate celelalte subcapitole ale disciplinei, te înscrii la cursul de pregătire.

Te înscrii, alegi în cont când începe cursul și plătești prima lună prin transfer bancar. Pentru a vedea mai întâi cum este prezentată materia, poți reveni la primul subcapitol al capitolului.

Acces la suportul de curs

25 RON / lună, fără ședințe

Ce cuprinde:

  • Acces la toate lecțiile disponibile
  • Suport de curs pentru tematica științifică și metodică
  • Exemple, explicații și exerciții
  • Acces la materialele noi adăugate pe platformă
  • Posibilitatea de a adresa întrebări

Poți alege și variante cu ședințe online, în grup sau individuale. Le vezi pe pagina cursului.

Ai întrebări sau o problemă? Scrie-mi pe WhatsApp, la 0745 874 576.

Înscrie-te Alte varianteCum plătești Login

Surse (3)
  • Ministerul Educației, subiecte și bareme pentru examenul național de definitivare în învățământ, disciplina Informatică, 2012–2025
  • Miloșescu, M., „Informatică. Manual pentru clasa a IX-a, profilul real, intensiv”, Editura Didactică și Pedagogică, București, 2005
  • „Tutorialul de Python”, documentația oficială a limbajului Python, https://docs.python.org/ro/3/tutorial/index.html
Actualizat: 20 octombrie 2026