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.
VA ROGG AM NEVOIEE RAPIDD!!!DAU COROANA
Răspunsuri la întrebare
Răspuns:
#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;
}