Faktorizacija 2
| vreme | memorija | ulaz | izlaz |
|---|---|---|---|
| 1 s | 128 Mb | standardni izlaz | standardni ulaz |
Za brojeve p i q kažemo da su k-prosto udaljeni ukoliko su oni prosti i između njih postoji tačno k prostih brojeva. Vama su dati brojevi N i k. Poznato je da je broj N ili prost ili se može zapisati u obliku proizvoda p1·p2·p3·...·pm, gde za svako 1 ≤ i ≤ m - 1 važi pi < p_{i+1} i pi i p_{i+1} su k-prosto udaljeni brojevi. Nažalost, mi ne znamo broj m niti brojeve pi - vaš zadatak je da faktorisete broj N, tj. da ga napišete u obliku proizvoda prostih brojeva.
U jednom test primeru je potrebno faktorisati više brojeva N.
U prvom redu standardnog ulaza se nalazi prirodan broj T - broj parova (N, k) iz opisa problema. U svakom od narednih T redova se nalaze, redom, brojevi N i k, razdvojeni razmakom.
Na standarni izlaz je potrebno ispisati T redova pri čemu je u i-tom redu potrebno ispisati faktorizaciju i-tog broja N sa ulaza. Činioce broja N ispisati u rastućem poretku i između svaka dva činioca ispisati znak '*' (zvezdica) bez razmaka i navodnika (videti dati primer).
1 ≤ T ≤ 5.000
2 ≤ N ≤ 1.000.000.000.000
0 ≤ k ≤ 100
4
238 2
11 0
2431 0
10 1
2*7*17
11
11*13*17
2*5
Npr. u prvom paru (N = 238, k = 2), brojevi 2 i 7 su k-prosto udaljeni jer su oni prosti i između njih se nalaze tačno dva prosta broja: 3 i 5. Slično i za brojeve 7 i 17. Faktorizacija broja N pod navedenim uslovima je, naravno, jedinstvena.
Morate biti ulogovani kako biste poslali zadatak na evaluaciju.