Fișierul intrare/ieșire	prime1.in, prime1.out	Sursă	ONI 2017 clasa a 5-a
Autor	Emanuela Cerchez	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	1.2 sec	Limită de memorie	24576 KB
Scorul tău	N/A	Dificultate	4

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Prime1 (clasa a 5-a)

Eu sunt fascinată de numerele prime. Consider că numerele prime sunt “scheletul” tuturor numerelor sau “atomii” acestora, pentru că orice număr natural mai mare decât 1 poate fi scris ca un produs de numere prime. Recent am aflat și alte proprietăți interesante legate de numerele prime, de exemplu:

1. În șirul Fibonacci există o infinitate de numere prime. Vă mai amintiți șirul Fibonacci? 0, 1, 1, 2, 3, 5, 8, 13, ... Este șirul în care fiecare termen, exceptând primii doi, se obține ca suma celor doi termeni care îl precedă.
2. Există numere naturale denumite „economice”. Un număr natural este economic dacă numărul de cifre necesare pentru scrierea sa este mai mare decât numărul de cifre necesare pentru scrierea descompunerii sale în factori primi (adică decât numărul de cifre necesare pentru scrierea factorilor primi și a puterilor acestora). De exemplu 128 este economic pentru că 128 se scrie cu 3 cifre, iar descompunerea sa în factori primi se scrie cu două cifre (2⁷); 4374 este economic pentru că se scrie cu 4 cifre, în timp ce descompunerea sa în factori primi se scrie cu 3 cifre (2*3⁷). Observați că atunci când un factor prim apare la puterea 1, aceasta nu este necesar să fie scrisă.
3. Multe numere naturale pot fi scrise ca sumă de două numere prime. Dar nu toate. De exemplu, 121 nu poate fi scris ca sumă de două numere prime.

Cerință

Scrieți un program care citește numărul natural n și o secvență de n numere naturale, apoi rezolvă următoarele cerințe:

1. determină și afișează câte dintre numerele din secvența dată sunt numere prime din șirul Fibonacci;
2. determină și afișează câte dintre numerele din secvența dată sunt numere economice;
3. determină și afișează câte dintre numerele din secvența dată nu pot fi scrise ca sumă de două numere prime.

Date de intrare

Fișierul de intrare prime1.in conține pe prima linie un număr natural c care reprezintă cerința (1, 2 sau 3). Pe a doua linie se află numărul natural n. Pe a următoarele n linii se află n numere naturale, căte unul pe linie.

Date de ieșire

Fișierul de ieșire prime1.out va conține o singură linie pe care va fi scris răspunsul la cerința din fișierul de intrare.

Restricții

• 1 < n ≤ 50
• Dacă c=1 sau c=3 numerele naturale din șir sunt mai mari decât 1 și mai mici decât 10⁷.
• Dacă c=2 numerele naturale din șir sunt mai mari decât 1 și mai mici decât 10¹⁴.
• Pentru rezolvarea corectă a cerinței 1 se acordă 20 de puncte; pentru rezolvarea corectă a cerinței 2 se acordă 50 de puncte, iar pentru rezolvarea corectă a cerinței 3 se acordă 30 de puncte.

Exemplu