LightOJ - 1035 - Intelligent Factorial Factorization

1. /****************#####    بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم   #####******************
2. __________________________________________________________________________
3. ######################  Ya-Seen Arafat(ACWizard) #########################
4. ######################        UAP-CSE-33B        #########################
5. *************************************************************************/
6. #include <bits/stdc++.h>
7. #define ll long long
8. #define S 103
9. using namespace std;
10.  
11. int prime[S];
12. int primeNum[S];
13. int ans[S];
14. int ind;
15.  
16. void seive(){
17.     int sqr = sqrt(S);
18.     for(int i = 2; i <= sqr; i++){
19.         if(prime[i]){
20.             for(int j = i+i; j < S; j+=i)prime[j] = 0;
21.         }
22.     }
23.     ind = 0;
24.     for(int i = 2; i < S; i++)if(prime[i])primeNum[ind++] = i;
25. }
26.  
27. void numDivisor(int number){
28.     int cn = 0;
29.     for(int i = 0; i < ind; i++){
30.         for(int k = 2; k <= number; k++){
31.             while(prime[k]%primeNum[i] == 0){
32.                 cn++;
33.                 prime[k] /= primeNum[i];
34.             }
35.             ans[primeNum[i]] += cn;
36.             cn = 0;
37.         }
38.     }
39. }
40.  
41. int main(){
42.     int  t, cs = 0, n;
43.     memset(prime, 1, sizeof(prime));
44.     seive();
45.     scanf("%d", &t);
46.     while(t--){
47.         scanf("%d", &n);
48.         memset(ans, 0, sizeof(ans));
49.         for(int i = 2; i < S; i++)prime[i] = i;
50.         numDivisor(n);
51.         printf("Case %d:", ++cs);
52.         bool flag = true;
53.         for(int i = 2; i <= 100; i++){
54.             if(ans[i] && flag)printf(" %d = %d (%d)", n, i, ans[i]), flag = false;
55.             else if(!flag && ans[i])printf(" * %d (%d)", i, ans[i]);
56.         }
57.         puts("");
58.     }
59.     return 0;
60. }