Problem G
Vittu betur

Nú fer að styttast í fyrstu umferð nýrrar spurningakeppni þar sem háskólar á höfuðborgarsvæðinu keppast um að komast að því hvaða skóli er klárastur. Í þessari keppni snúast allar spurningarnar um að frumþátta tölur og það er alveg bannað að giska, sama hversu vel það er gert. Þú varst valin í lið Háskóla Íslands um leið og það spurðist út að frændi þinn væri spurningahöfundur. Aðspurður sagði frændi þinn: ‘Allar tölurnar sem ég ætla að láta ykkur þátta verða á forminu $n!$, þar sem $n$ er jákvæð heiltala minni eða jöfn ${10}^6$. Hvernig á þessi vitneskja þó eftir að hjálpa þér? Ætlarðu að forreikna allar niðurstöðurnar og leggja þær á minnið?’. Það er þó einmitt það sem þú og liðsfélagir þínir ætla að gera. Fyrst þarftu þó að skrifa forrit sem getur frumþáttað $n!$ fyrir gefið $n$.

Inntak

Sérhver lína inntaksins inniheldur heiltölu $0\le n\le {10}^6$. Inntakið mun innihalda mest ${10}^5$ línur.

Úttak

Stjórnendum sjónvarpstöðvarinnar sem sendir út keppnina leist ekkert á hversu löng svörin gætu orðið og skipuðu því frænda þínum að leggja fyrir lægri tölur. Sem málamiðlun var ákveðið að það myndi nægja að liðin segðu hversu marga frumþætti gefin tala hefur, talið með margfeldni. Nánar tiltekið, fyrir sérhvert $n$ í inntakinu má rita $n!=\prod _{i=0}^k{p}_i^{e_i}$ þar sem $p_i$ er frumtala fyrir öll $i$ og prenta skal $\sum _{i=0}^k{e}_i$ á sinni eigin línu.

1
2
3
4
5
6
7
8
9
10

0
1
2
4
5
7
8
11
13
15