Light Oj: 1035 - Intelligent Factorial Factorization

light oj: 1035 - Intelligent Factorial Factorization


#include <iostream>
#include <cstdio>
#include <math.h>
#define max 1000000
using namespace std;
int a[max];
int prime[max];


int main()
{
    int p,c,x,i,j,num,test,ary[100000],temp,count=0,lastprime;

    for(i=3;i<=sqrt(max);i+=2){
      if(a[i]==0){
         for(j=i*i;j<=max;j+=i){
            a[j]=1;
        }
      }
   }
  prime[count++]=2;
    for(i=3;i<=max;i+=2){
      if(a[i]==0){
        prime[count++]=i;
    }
}
     cin>>test;
     for(x=1;x<=test;x++){
        cin>>num;
        c=0;
        for(i=0;prime[i]<=num;i++){

                   temp=num;
                     p=0;
                    while(temp!=0){
                    p=p+temp/prime[i];
                    temp=temp/prime[i];
                }


             ary[c]=p;
             c++;
        }
        lastprime=prime[i-1];
            printf("Case %d: %d = ",x,num);
         for(j=0;prime[j]<=num;j++){
            printf("%d (%d)",prime[j],ary[j]);
            if(prime[j]<lastprime){
                printf(" * ");
            }
         }
        cout<<endl;

     }



    return 0;
}