Enunțul problemei prime, de clasa a 5-a, dată în 2017 la ONI, se găsește pe PbInfo și .campion.

Rezumat prime

Pentru n numere naturale ce se citesc din fișierul de intrare, trebuie să răspundem la una dintre următoarele cerințe:

  1. Să se afișeze numărul de numere prime dintre cele date ce aparțin șirului lui Fibonacci.
  2. Să se afișeze numărul de numere economice dintre cele date. Un număr se consideră economic dacă în scrierea sa se folosesc mai multe cifre decât în scrierea descompunerii sale în factori primi. Cea din urmă este suma numărului de cifre folosite pentru scrierea factorilor primi și a exponenților acestora. Exponentul 1 nu se scrie.
  3. Să se afișeze numărul de numere dintre cele date ce pot fi scrise ca sumă de două numere prime.

Soluție prime

Pentru prima cerință, observăm că sunt foarte puține numere ce îndeplinesc condiția dată, mai mici decât 107. Acestea sunt 2, 3, 5, 13, 89, 233, 1597, 28657 și 514229. Le putem reține într-un vector global, iar atunci când testăm dacă un număr respectă proprietatea dată, pur și simplu îl căutăm în acest vector.

Pentru a doua cerință, avem nevoie doar de o modalitate eficientă de a descompune numerele în factori primi. Aceasta constă în a găsi la începutul programului numerele prime mai mici decât rădăcina pătrată a celei mai mari valori din vector (vMax), folosind ciurul lui Eratostene. Apoi, efectuăm descompunerea în factori primi a numerelor date folosind direct numerele prime găsite mai înainte. Am definit și o funcție nrDigits ce calculează numărul de cifre ale numărului transmis ca parametru, pentru a testa mai ușor condiția din enunț.

Folosim și la a treia cerință ciurul lui Eratostene, dar de data asta nu până la sqrt(vMax), ci chiar până la vMax. Când testăm dacă un număr x se poate scrie ca sumă de două numere prime, pentru fiecare număr prim mai mic sau egal ca el (primul număr) verificăm folosind vectorul sieve (ciurul) dacă diferența până la x (al doilea număr) este un număr prim. Dacă da, numărul curent este bun, deci incrementăm soluția.

Sursă C++ prime

Dacă ai vreo nedumerire cu privire la problema prime, lasă un comentariu și te voi ajuta 🙂

Îți place conținutul acestui site?

Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!