Mysterious Bacteria LightOJ - 1220

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cmath>
 4 #include <vector>
 5 using namespace std;
 6 typedef long long ll;
 7 const int N = 1e6+10;
 8 int prime[N],cnt;
 9 bool st[N];
10 vector<int> v;
11 void GetPrime(int n)
12 {
13     for(int i=2;i<=n;i++)
14     {
15         if(!st[i]) prime[++cnt] = i;
16         for(int j=1;prime[j]<=n/i;j++)
17         {
18             st[i*prime[j]] = 1;
19             if(i%prime[j]==0) break;
20         }
21     }
22 }
23 int GetDivide(ll n)
24 {
25     for(int i=1;prime[i]<=n/prime[i];i++)
26     {
27         if(n%prime[i]==0)
28         {
29             int s = 0;
30             while(n%prime[i]==0) n/=prime[i],s++;    
31             v.push_back(s);
32         }
33     }
34     if(n>1) v.push_back(1); 
35     sort(v.begin(),v.end());
36     return v[0];
37 }
38 int main()
39 {
40 //    freopen("in.txt","r",stdin);
41     GetPrime(1e6);
42     int T,kcase = 0;
43     scanf("%d",&T);
44     while(T--)
45     {
46         v.clear();
47         ll n,tmp; scanf("%lld",&n);
48         if(n<0) tmp = -n;
49         else tmp = n;
50         int ans = GetDivide(tmp);
51         while(n<0&&!(ans&1)) ans>>=1;    
52         printf("Case %d: %d\n",++kcase,ans);
53     }
54     return 0;
55 }