Probleme recurente si implementari eficiente (ciurul lui Eratostene, exponentieri rapide)

Problemele recurente apar frecvent în informatică, unde aceeași operație se repetă de mai multe ori. Optimizarea acestor operații este crucială pentru performanță. Două tehnici fundamentale sunt ciurul lui Eratostene și exponentierea rapidă.

Ciurul lui Eratostene este o metodă eficientă de a găsi toate numerele prime până la o limită dată N. Algoritmul clasic are complexitate O(N log log N) și se bazează pe marcarea iterativă a multiplilor numerelor prime. Implementarea eficientă presupune:

• Folosirea unui vector boolean de dimensiune N+1, inițializat cu true (toate numerele sunt considerate prime).
• Parcurgerea i de la 2 la sqrt(N); dacă i este prim, se marchează ca false toți multiplii lui i începând cu i*i (deoarece multiplii mai mici au fost deja marcați de numere prime mai mici).
• La final, toate pozițiile rămase true sunt numere prime.

Exponentierea rapidă (ridicarea la putere în O(log n)) este esențială pentru calcule modulare în criptografie și probleme de optimizare. Ideea de bază: pentru a calcula a^b, împărțim b în jumătăți recursive. Dacă b este par, a^b = (a^(b/2))^2; dacă b este impar, a^b = a * a^(b-1).

Implementarea iterativă folosește reprezentarea binară a lui b: se parcurg biții lui b de la cel mai puțin semnificativ; dacă bitul curent este 1, se înmulțește rezultatul cu a; la fiecare pas, a se ridică la pătrat. Complexitatea este O(log b).

Combinația acestor tehnici apare frecvent în probleme de concurs: de exemplu, calculul sumelor de puteri modulo M pentru numere prime dintr-un interval. Înțelegerea profundă a recurențelor și a optimizărilor permite scrierea unui cod elegant și rapid.

Exemple

• Exemplul 1: Ciurul lui Eratostene – Găsiți toate numerele prime mai mici decât 30. Implementare în C++: vector<bool> prim(31, true); for (int i=2; i*i<=30; i++) if (prim[i]) for (int j=i*i; j<=30; j+=i) prim[j]=false; Rezultat: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
• Exemplul 2: Exponențiere rapidă – Calculați 3^13 mod 100. Reprezentarea binară a lui 13: 1101 (8+4+1). Algoritm: rez=1, a=3. Bitul 0 (1): rez=3, a=3^2=9. Bitul 1 (0): a=9^2=81. Bitul 2 (1): rez=3*81=243 mod 100=43, a=81^2=6561 mod 100=61. Bitul 3 (1): rez=43*61=2623 mod 100=23. Răspuns: 23.
• Exemplul 3: Combinație – Folosind ciurul, găsiți primele 10 numere prime, apoi calculați suma pătratelor lor modulo 10^9+7 cu exponentiere rapidă. Se aplică ciurul până la 30, se extrag primele 10: 2,3,5,7,11,13,17,19,23,29. Pentru fiecare, se calculează pătratul (2^2=4, 3^2=9, ...) și se însumează. Rezultat final: 4+9+25+49+121+169+289+361+529+841 = 2397.

Concepte cheie: Ciurul lui Eratostene – găsirea numerelor prime până la N în O(N log log N), Exponentiere rapidă – ridicarea la putere în O(log n) folosind biți, Optimizarea recurențelor prin reducerea complexității