Lightoj 1035 - Intelligent Factorial Factorization

http://lightoj.com/volume_showproblem.php?problem=1035

1. #include <stdio.h>
2. #include <string.h>
3. #include <stdlib.h>
4. #include <ctype.h>
5. #include <math.h>
6. #include <limits.h>
7. #include <set>
8. #include <algorithm>
9. #include <iostream>
10. #include <vector>
11. #include <stack>
12. #include <string>
13. #include <list>
14. #include <map>
15. #include <queue>
16. #include <sstream>
17. #include <utility>
18. #define pf(a) printf("%d\n",a)
19. #define pf2(a,b) printf("%d %d\n",a,b)
20. #define pfcs(cs,a) printf("Case %d: %d\n",cs,a)
21. #define sc(a) scanf("%d",&a)
22. #define sc2(a,b) scanf("%d %d",&a,&b)
23. #define pb push_back
24. #define mp make_pair
25. #define pi acos(-1.0)
26. #define ff first
27. #define LL long long
28. #define ss second
29. #define rep(i,n) for(i = 0; i < n; i++)
30. #define REP(i,n) for(i=n;i>=0;i--)
31. #define FOR(i,a,b) for(int i = a; i <= b; i++)
32. #define ROF(i,a,b) for(int i = a; i >= b; i--)
33. #define re return
34. #define QI queue<int>
35. #define SI stack<int>
36. #define pii pair <int,int>
37. #define MAX
38. #define MOD
39. #define INF 1<<30
40. #define SZ(x) ((int) (x).size())
41. #define ALL(x) (x).begin(), (x).end()
42. #define sqr(x) ((x) * (x))
43. #define memo(a,b) memset((a),(b),sizeof(a))
44. #define G() getchar()
45. #define MAX3(a,b,c) max(a,max(b,c))
46.  
47. double const EPS=3e-8;
48. using namespace std;
49.  
50.  
51. template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
52. template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
53. int ans[200][200],now[105];
54. vector <int> prime;
55. void pre()
56. {
57.        int i,j;
58.        prime.pb(2);
59.        for(i=3;i<=100;i+=2)
60.        {
61.               if(!now[i])
62.               {      prime.pb(i);
63.                      for(j=i*i;j<=100;j+=(2*i))
64.                      now[j]=1;
65.               }
66.        }
67.        for(i=2;i<=100;i++)
68.        {
69.               int n=i;
70.               for(j=0;j<prime.size();j++)
71.               {
72.                      if(n%prime[j]==0)
73.                      {
74.                             int ct=0;
75.                             while(n%prime[j]==0)
76.                             {
77.                                    n/=prime[j];
78.                                    ct++;
79.                             }
80.                             ans[i][prime[j]]=ct;
81.                      }
82.                      ans[i][prime[j]]+=ans[i-1][prime[j]];
83.               }
84.        }
85. }
86. int main()
87. {
88.  
89.     //freopen("in.txt", "r", stdin);
90.     pre();
91.     int cs,t,n,i;
92.     scanf("%d",&t);
93.     FOR(cs,1,t)
94.     {
95.            scanf("%d",&n);
96.            printf("Case %d: %d =",cs,n);
97.            int ct=0;
98.            for(i=0;i<prime.size();i++)
99.            {
100.                   if(ans[n][prime[i]])
101.                   {
102.                          if(ct++) printf(" *");
103.                          printf(" %d (%d)",prime[i],ans[n][prime[i]]);
104.                   }
105.            }
106.            printf("\n");
107.     }
108.  
109.  
110.  
111. }