Fişierul intrare/ieşire:prime1.in, prime1.outSursăONI 2017 clasa a 5-a
AutorEmanuela CerchezAdăugată defrancuCristian Francu francu
Timp execuţie pe test1.2 secLimită de memorie24576 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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 (27); 4374 este economic pentru că se scrie cu 4 cifre, în timp ce descompunerea sa în factori primi se scrie cu 3 cifre (2*37). 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 107.
  • Dacă c=2 numerele naturale din şir sunt mai mari decât 1 şi mai mici decât 1014.
  • 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

prime1.inprime1.outExplicaţie
1
5
2
10
13
997
233
3
Cerinţa este 1. Cele 3 numere prime din şirul Fibonacci existente în secvenţă sunt 2, 13 şi 233.
2
4
128
25
4374
720
2
Cerinţa este 2. Succesiunea conţine două numere economice (128 şi 4374).
3
5
57
30
121
11
3
4
Cerinţa este 3. Sunt 4 numere naturale din secvenţă care nu pot fi scrise ca sumă de două numere prime: 57, 121, 11, 3.
Trebuie sa te autentifici pentru a trimite solutii. Click aici