LightOJ - 1289 - LCM From 1 to n

Idea: LCM from 1 to n is the highest power of primes less than or equal to n.We can precalculate the primes.Use bitwise seive for generating Prime upto 10^8.

Code First Then See Solution

Code:
#include <bits/stdc++.h>

#define ll  unsigned

using namespace std;

const int MAX = 100000000;
const int LMT =     10000;

int _c[(MAX>>6)+1];

ll  p[5761482];

#define IsComp(n)  (_c[n>>6]&(1<<((n>>1)&31)))

#define SetComp(n) _c[n>>6]|=(1<<((n>>1)&31))
ll mnt=0;
void sieve()
{
    int x=0;

    for (int i = 3; i <= LMT; i += 2)
        if (!IsComp(i))
            for (int j = i*i; j <= MAX; j += i+i)
                SetComp(j);

    p[x++]=2;
    mnt++;
    for (int i=3; i <= MAX; i += 2)
        if (!IsComp(i))
        {
            p[x++]=i;
            mnt++;
        }
}

ll store[5761482];

ll precal()
{
    store[0]=2;
    for(ll i=1;i<mnt;i++)
    {
        store[i]=store[i-1]*p[i];
    }
}

ll cal(ll n)
{
    ll temp,sum=1;
    ll x=sqrt(n);
    for(ll i=0;i<mnt&&p[i]<=x;i++)
    {
        temp=n;
        temp/=p[i];
        while(temp>=p[i])
        {
            temp/=p[i];
            sum*=p[i];
        }
    }
    return sum;
}

int main()
{
    int t,f=0;
    sieve();
    precal();
    cin>>t;
    while(t--)
    {
        f++;
        ll n,ans;
        cin>>n;
        ans=cal(n);
        ll u=upper_bound(p,p+mnt,n)-p;
        u--;
        ans*=store[u];
        cout<<"Case "<<f<<": "<<ans<<endl;
    }
    return 0;

}