Rezolvare completă PbInfo #3316 Eratostene5

Cerința

Se dau n numere naturale nenule şi se notează cu P produsul acestora. Să se afle numerele prime din descompunerea lui P în factori primi, precum şi exponentul acestora.

Date de intrare

Fișierul de intrare eratostene5.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire eratostene5.out va conține pe fiecare linie un număr prim din descompunerea lui P şi exponentul acestuia. Factorii primi se vor afişa în ordine crescătoare.

Restricții și precizări

  • 1 ≤ n ≤ 500.000
  • numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000

Exemplu

eratostene5.in

4
6 10 21 56

eratostene5.out

2 5
3 2
5 1
7 2

Explicație

Numărul P este 6•10•21•56=25•32•51•72.

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 Eratostene5:

#include <fstream>
#define N 1000000
using namespace std;
ifstream fi("eratostene5.in");
ofstream fo("eratostene5.out");
int i, j, n, x, k;
int p[N+1], a[N+1][8], e[N];

int main()
{
    //ciurul lui eratostene + numararea si memorarea factorilor primi din descompunere
    p[1] = 1;
    a[1][0] = 0;
    for(i = 2; i <= N; i++)
        if(p[i]==0)
    {
        a[i][0] = 1;
        a[i][1] = i;
        j = i+i;
        while(j <= N)
        {
            p[j] = 1;
            a[j][0]++;
            a[j][a[j][0]] = i;
            j = j + i;
        }
    }

    //prelucrare sir
    fi >> n;
    for(i = 1; i <= n; i++)
    {
        fi >> j;
        x = j;
        for(k = 1; k <= a[j][0]; k++)
            while(x % a[j][k] == 0)
            {
                e[a[j][k]]++;
                x = x / a[j][k];
            }
    }
    for(i = 2; i < N; i++)
        if(e[i] > 0) fo << i << " " << e[i] << "\n";
    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 #3316 Eratostene5

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3316 Eratostene5 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!