Lightoj 1289 - LCM from 1 to n

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

1. #include<cstdio>
2. #include<iostream>
3. #include<cstring>
4. #include<cstdlib>
5. #include<cmath>
6. #include<algorithm>
7. #include<string>
8. #include<map>
9. #include<set>
10. #include<vector>
11. #include<queue>
12. #include<bitset>
13.  
14. using namespace std;
15.  
16. #define clr( x , y ) memset(x,y,sizeof(x))
17. #define cls( x ) memset(x,0,sizeof(x))
18. #define mp make_pair
19. #define pb push_back
20. typedef long long lint;
21. typedef long long ll;
22. typedef long long LL;
23. const int maxn = 1e8 + 5 ;
24. const int pnum = 5761460 ;
25. bitset<maxn>noprime ;
26. unsigned int mul[pnum] ;
27. int p[pnum] , len ;
28. int sieve(){
29.     noprime.reset() ;
30.     for( int i = 2 ; i * i <= maxn ; i++ ){
31.         if( !noprime[i] ){
32.             for( int j = i * i ; j <= maxn ; j += i ){
33.                 noprime[j] = 1 ;
34.             }
35.         }
36.     }
37.     int k = 0 ;
38.     for( int i = 2 ; i <= maxn ; i++ )
39.         if( !noprime[i] ) p[k++] = i ;
40.     return k ;
41. }
42.  
43. void init_lcm(){
44.     len = sieve() ;
45.     mul[0] = p[0] ;
46.     for( int i = 1 ; i < len ; i++ )
47.         mul[i] = mul[i-1] * p[i] ;
48. }
49.  
50. void solve( int n ){
51.     int pos = lower_bound( p , p + len , n ) - p ;
52.     if( p[pos] != n ) pos-- ;
53.     unsigned int ans = mul[pos] ;
54.     for( int i = 0 ; p[i] * p[i] <= n ; i++ )
55.     {
56.         int tmp = p[i] ;
57.         int tmp2 = p[i] * p[i] ;
58.         while( tmp2 / tmp == p[i] && tmp2 <= n )
59.         {
60.             tmp = tmp * p[i] ;
61.             tmp2 = tmp2 * p[i] ;
62.         }
63.         ans = ans * ( tmp / p[i] ) ;
64.     }
65.     cout << ans << endl ;
66. }
67. int main(){
68. // freopen("input.txt","r",stdin);
69.     int t ; cin >> t ; int kase = 1 ;
70.     init_lcm() ;
71.     while( t-- ){
72.         int n ;
73.         cin >> n ;
74.         printf( "Case %d: " , kase++ ) ;
75.         solve( n ) ;
76.     }
77.     return 0;
78. }