Rezolvare completă PbInfo #2129 Prime1

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^7); 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^7). 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ța

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 treia linie se află o secvenţă de n numere naturale separate prin spaţii.

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 și precizări

  • 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^7.
  • Dacă c=2 numerele naturale din şir sunt mai mari decât 1 şi mai mici decât 10^14.
    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.

Exemplul 1

prime1.in

1
5
2 10 13 997 233

prime1.out

3

Exemplul 2

prime1.in

2
4
128 25 4374 720

prime1.out

2

Exemplul 3

prime1.in

3
5
57 30 121 11 3

prime1.out

4

Explicații

Pentru exemplul 1: Cerinţa este 1. Cele 3 numere prime din şirul Fibonacci existente în secvenţă sunt 2, 13 şi 233.

Pentru exemplul 2: Cerinţa este 2. Succesiunea conţine două numere economice (128 şi 4374).

Pentru exemplul 3: 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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Prime1:

//Emanuela Cerchez
#include <fstream>
#include <cmath>
#define VMAX 10000001
#define PMAX 1000000
#define NMAX 50
using namespace std;
ifstream fin("prime1.in");
ofstream fout("prime1.out");

bool ciur[VMAX];
int nrprim, nr, n;
int prim[PMAX];
int lgprim[PMAX];
long long int a[NMAX], vmax;
int fib[NMAX];
int nrfib;

int main()
{int cerinta, i, j, d, lg, lgx, f1, f2, f3, p, gasit;
 long long int cx;
 fin>>cerinta>>n;
 for (i=0; i<n; i++)
     {
        fin>>a[i];
        if (a[i]>vmax) vmax=a[i];
     }
 //ciur
 if (cerinta==2) vmax=sqrt((double)vmax);
 ciur[0]=ciur[1]=1;
 for (d=2; d*d<=vmax; d++)
      if (!ciur[d])
          for (j=d*d; j<=vmax; j+=d)
              ciur[j]=1;
 //transfer intr-un vector numerele prime <=vmax
 prim[0]=2; nrprim=1; lgprim[0]=1;
 for (d=3; d<=vmax; d+=2)
      if (!ciur[d])
         {prim[nrprim]=d;
          cx=d; do {cx/=10; lgprim[nrprim]++;} while (cx);
          nrprim++;
         }
 if (cerinta==1)
    {
     for (f1=f2=1; f1+f2<=vmax; )
         {
          f3=f1+f2; f1=f2; f2=f3;
          if (!ciur[f3]) fib[nrfib++]=f3;
         }
     nr=0;
     for (i=0; i<n; i++)
         {
          for (j=0; j<nrfib && a[i]!=fib[j]; j++);
          if (j<nrfib) nr++;
         }
     fout<<nr<<'\n';
     fout.close();
     return 0;
    }

 if (cerinta==2)
    {nr=0;
     //descompunere in factori primi eficient
     for (i=0; i<n; i++)
         {
          cx=a[i]; lgx=0; do {lgx++; cx/=10;} while (cx);
          lg=0;
          for (j=0; j<nrprim && prim[j]*prim[j]<=a[i] && lg<lgx; j++)
             {
              for (p=0; a[i]%prim[j]==0; p++,a[i]/=prim[j]);
              if (p)
                 {
                   lg+=lgprim[j];
                   if (p>1) {cx=p; do {lg++; cx/=10;} while (cx);}
                 }
              }
         if (a[i]>1)
            {cx=a[i]; do {lg++; cx/=10;} while (cx);}
         if (lg<lgx)
             nr++;
         }
      fout<<nr<<'\n';
      fout.close();
      return 0;
      }
//cerinta 3
nr=0;
for (i=0; i<n; i++)
     {for (gasit=j=0; j<nrprim && a[i]>prim[j]; j++)
         if (!ciur[a[i]-prim[j]]) {gasit=1; break;}
      if (!gasit) nr++;}
fout<<nr<<'\n';
fout.close();
return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #2129 Prime1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2129 Prime1 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!