Uva 884 - Factorial Factors

Problem Link:: Uva Factorial Factors

 // Verdict:: Accepted

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#define sf scanf
#define pf printf
#define LL long long
#define Lo long
#define ull unsigned long long
#define ul unsigned long
#define ui unsigned int
#define mx 1000100

using namespace std;

template<class T> T gcd(T a, T b){return b<=0?a:gcd(b,a%b);}
template<class T> T lcm(T a, T b){return (a / (gcd(a,b))) * b; }
template<class T> T setbit(T n, T pos) {n = n|(1<<pos); return n;}
template<class T> T checkbit(T n, T pos) {n = n&(1<<pos); return n;}

ull prime[mx],prm[(mx/2)+1],plen=0;

void seieve(ull n)
{
    ull i,j,x=(long)sqrt(double(n));

    prime[0]=setbit<ull>(prime[0],0);
    prime[0]=setbit<ull>(prime[0],1);

    for(i=4;i<=n;i+=2)
    {
        prime[i>>5]=setbit<ull>(prime[i>>5],i&31);
    }

    for(i=3;i<=x;i+=2)
    {
        if(!(checkbit<ull>(prime[i>>5],i&31)))
        {
            for(j=i*i;j<=n;j+=i)
            {
                prime[j>>5]=setbit<ull>(prime[j>>5],j&31);
            }
        }
    }


    for(i=2;i<=n;i++)
    {
        if(!(checkbit<ull>(prime[i>>5],i&31)))
        {
            prm[plen++]=i;
        }
    }

    //for(i=0;i<plen;i++)cout << prm[i] << endl;
}

ull factor(ull n)
{
    ull i,cnt=0; ull s;

    //mp.clear();

    for(i=0;i<plen and prm[i] * prm[i] <= n ; i++)
    {
        if(!(n%prm[i]))
        {
            //s=0;

            while(!(n%prm[i]))
            {
                //mp[prm[i]]++;
                s++;
                cnt++;
                n/=prm[i];
                if(n==0 or n==1) break;
            }

            //cout << mp[prm[i]] << " ";
            //s+=mp[prm[i]];
            //s+=cnt;
        }
    }

    if(n>1)
    {
        //s+=1;
        cnt++;
        //s+=cnt;
    }

    //cout << "cnt = " << cnt;
    //cout << "s = " << s;

    return cnt;
}

ull res[mx];

int main()
{
    seieve(mx);

    // Cumulative Sum
    for(ull i=2;i<=mx;i++)
    {
        res[i]=factor(i)+res[i-1];
    }

    ull n;

    while(1==sf("%llu",&n))
    {
        pf("%llu\n",res[n]);
    }

    return 0;
}