Uva 884 Solution

#include<bits/stdc++.h>
#define ll long long int
#define N 1000001
using namespace std;
int p[N+1];
vector<int>a;
void prime()
{
    ll i, j, l = sqrt(N);
    p[0] = p[1] = 1;
    a.push_back(2);
    for(i=4;i<=N;i+=2)
        p[i] = 1;
    for(i=3;i<=N;i+=2)
    {
        if(p[i] == 0)
        {
            a.push_back(i);
            if(i <= l)
            {
                for(j=i*i;j<=N;j+=i*2)
                    p[j] = 1;
            }
        }
    }
}
int f[N+1];
void logic()
{
    prime();
    ll i;
    for(i=2;i<=N;i++)
    {
        f[i] = f[i-1];
        ll t = i, j = 0;
        while(p[t] != 0)
        {
            if(t%a[j] == 0)
            {
                f[i]++;
                t /= a[j];
            }
            else
                j++;
        }
        if(p[t] == 0)
            f[i]++;
    }
}
int main()
{
    logic();
    ll n;
    while(cin >> n)
    {
        cout << f[n] << endl;
    }

    return 0;
}