lightoj1035

CODE

#include <iostream>
#include <cstring>
using namespace std;
int prime[105],ncase;
int vis[105];
int cnt;
int np[105][105];
int ans[105];
int main()
{
        int t;
        cin >> t;
        for(int i=2;i<105;i++) if(!vis[i])
        {
                prime[cnt++]=i;
                for(int j=i+i;j<105;j+=i)
                {
                        vis[j]=1;
                }
        }
        for(int i=2;i<=100;i++)
        {
                int n=i;
                for(int j=0;j<cnt&&n!=1;j++)
                {
                        int num=0;
                        while(n%prime[j]==0){num++;n/=prime[j];}
                        np[i][j]+=num;
                }
        }
        while(t--)
        {
                int n;
                cin >> n;
                memset(ans,0,sizeof(ans));
                for(int i=2;i<=n;i++)
                {
                        for(int j=0;j<cnt;j++)
                        {
                                ans[j]+=np[i][j];
                        }
                }
                int i=0;
                while(ans[i]==0)i++;
                cout <<"Case "<<++ncase<<": "<<n<<" = "<<prime[i]<<" ("<<ans[i]<<")";
                i++;
                for(;i<cnt;i++)
                {
                        if(ans[i]==0)continue;
                        cout << " * "<<prime[i]<<" ("<<ans[i]<<")";
                }
                cout << endl;
        }
        return 0;
}