Pe scurt
Această lecție prezintă trei algoritmi fundamentali din algoritmica de liceu: prelucrarea cifrelor unui număr, determinarea divizorilor și verificarea numerelor prime. Algoritmii se bazează pe operații repetitive de împărțire la 10 pentru cifre și pe testarea divizibilității până la rădăcina pătrată a numărului pentru divizori și primalitate. Eficiența algoritmică este esențială, urmărindu-se complexitatea O(√n) pentru divizori și numere prime.
Prelucrarea cifrelor unui număr
Descompunerea unui număr se realizează prin operații repetitive de împărțire la 10:
- Ultima cifră se obține prin
n % 10
- Eliminarea ultimei cifre se face prin
n = n / 10
Algoritmi clasici pentru prelucrarea cifrelor
- Suma cifrelor
- Oglinditul unui număr
- Numărul de cifre pare/impare
- Verificarea palindromului
Exemplu: Oglinditul unui număr
- Fie n = 1234
- Inițializăm oglindit = 0
- Cât timp n > 0:
- cifra = n % 10 = 4; oglindit = oglindit * 10 + cifra = 4; n = n / 10 = 123
- cifra = 3; oglindit = 43; n = 12
- cifra = 2; oglindit = 432; n = 1
- cifra = 1; oglindit = 4321; n = 0
Determinarea divizorilor unui număr
Definiție: Un divizor al lui n este un număr d astfel încât n % d == 0
Metoda simplă: Parcurgerea de la 1 la n
Optimizare: Parcurgerea până la sqrt(n) – dacă d este divizor, atunci și n/d este divizor
Exemplu: Divizorii lui 36
- Parcurgem i de la 1 la sqrt(36) = 6
- i=1: 36%1=0, afișăm 1 și 36
- i=2: 36%2=0, afișăm 2 și 18
- i=3: 36%3=0, afișăm 3 și 12
- i=4: 36%4=0, afișăm 4 și 9
- i=5: 36%5=1, nu este divizor
- i=6: 36%6=0, afișăm 6 (pentru a evita duplicarea, afișăm o singură dată)
- Divizorii sunt: 1, 36, 2, 18, 3, 12, 4, 9, 6
Aplicații: Suma divizorilor, numărul de divizori
Verificarea numerelor prime
Definiție: Numerele prime sunt numere naturale mai mari decât 1 care au exact doi divizori: 1 și el însuși
Algoritm de verificare
- Se testează divizibilitatea cu numere de la 2 până la
sqrt(n)
- Dacă se găsește vreun divizor, numărul nu este prim
Optimizări importante
- Tratarea separată a lui 2
- Testarea doar a numerelor impare
Exemplu: Verificare număr prim pentru n = 29
- Dacă n < 2, nu este prim
- Dacă n este 2, este prim
- Pentru n=29: calculăm sqrt(29) ≈ 5.38
- Testăm divizori: 29%2=1, 29%3=2, 29%4=1, 29%5=4
- Niciunul nu împarte exact, deci 29 este prim
Aplicații combinate și concepte cheie
Concepte cheie
- Prelucrarea cifrelor: extragerea ultimei cifre prin
n % 10, eliminarea prin n / 10
- Divizori: testarea până la
sqrt(n) pentru eficiență, afișarea perechilor (d, n/d)
- Numere prime: verificare cu condiția
n % i == 0 pentru i de la 2 la sqrt(n)
- Optimizări: tratarea separată a lui 2, testarea doar a numerelor impare
- Aplicații combinate: palindrom, număr prim circular, suma divizorilor
Exemple de combinare
- Verificarea dacă un număr este „prim circular” prin rotirea cifrelor
Verifică-te!
- Care este metoda de extragere a ultimei cifre a unui număr și cum se elimină aceasta?
- De ce este mai eficient să parcurgem până la sqrt(n) când căutăm divizorii unui număr?
- Ce condiție trebuie îndeplinită pentru ca un număr natural mai mare decât 1 să fie considerat prim?