(nensnt.*)

Bất kỳ một số nguyên dương (lớn hơn 1) nào cũng có thể biểu diễn được dưới dạng tích các số nguyên tố, ví dụ \(200 = 2 \times 2 \times 2 \times 5 \times 5\). Tuy nhiên để tiết kiệm khi in ra giấy người ta thường nén tích các số nguyên tố bằng cách:

+ Xóa hết các dấu nhân (dấu \(\times\))

+ Số nguyên tố nào lặp lại nhiều hơn 1 lần thì chỉ ghi số đó 1 lần, sau đó là số lần lặp lại của số nguyên tố đó được ghi trong cặp dấu ngoặc ( và )

+ Các số nguyên tố không lặp lại vẫn được giữ nguyên và theo sau nó là dấu cách

Ví dụ: \(100 = 2(2)5(2);\ 350 = 2\ 5(2)7\ \)

Yêu cầu: Cho số nguyên dương \(n\) \((1 < n \leq 10^{6})\), hãy tìm dạng nén khi biểu diễn số nguyên dương \(n\) thành tích các số nguyên tố

Dữ liệu vào:

+ Số nguyên dương \(n\)

Dữ liệu ra:

+ Ghi một dòng là dạng nén khi phân tích số \(n\) thành tích các số nguyên tố

Ví dụ: