Fișierul intrare/ieșire	factorization.in, factorization.out	Sursă	ad-hoc
Autor		Adăugată de	Alexandru Valeanu • AlexandruValeanu
Timp de execuție pe test	9.5 sec	Limită de memorie	4096 KB
Scorul tău	N/A	Dificultate	N/A

Vezi soluțiile trimise | Statistici

Factorizare (arhiva educațională)

Se dau T numere naturale.
Să se determine, pentru fiecare număr în parte, descompunerea sa în factori primi.

Dacă N = p₁^e₁^ * p₂^e₂^ * ... * p_k^e_k^, k ≥ 1 atunci se cere să se afișeze k perechi:

• p₁ e₁
• p₂ e₂
  .
  .
  .
• p_k e_k

Date de intrare

Fișierul de intrare factorization.in va conține T+1 linii.
Pe prima linie se va afla numărul natural T.
Pe următoarele T linii se va afla câte un număr natural N_i, 1 ≤ i ≤ T.

Date de ieșire

Fișierul de ieșire factorization.out va conține descompunerile în factori primi a celor T numere.
Între oricare 2 descompuneri se va afișa un rând liber.

Teste

Sunt 3 grupe de teste:

• Grupa 1 [20 puncte]
  • 1 ≤ T ≤ 500.000
  • 1 ≤ N_i ≤ 10⁶

• Grupa 2 [30 puncte]
  • 1 ≤ T ≤ 2.000
  • 1 ≤ N_i ≤ 10¹²

• Grupa 3 [50 puncte]
  • 1 ≤ T ≤ 30
  • 1 ≤ N_i ≤ 10³⁵

Precizări

• Fiecare număr conține cel mult un factor prim mai mare decât 10⁹!

Exemplu