Uva 11408 Solution

#include<bits/stdc++.h>
#define N 5000001
#define ll unsigned long long int
using namespace std;
int s[N+1];
void prime()
{
    ll i, j;
    ll l = sqrt(N);
    s[0] = s[1] = 1;
    for(i=2; i<=l; i++)
    {
        if(s[i] == 0)
        {
            for(j=2; i*j<=N; j++)
                s[i*j] = 1;
        }
    }
}

int p[N+1];
void seive()
{
    ll i, j;
    for(i=1; i<=N; i++)
        p[i] = i;
    for(i=4; i<=N; i+=2)
        p[i] = 2;
    for(i=3; i*i<=N; i++)
    {
        if(p[i] == i)
        {
            for(j=i*i; j<=N; j+=i)
            {
                if(p[j] == j)
                    p[j] = i;
            }
        }
    }
}

int c[N+1];
void getfactor()
{
    ll i, j;
    for(i=2; i<=N; i++)
    {
        ll s = 0;
        ll n = i;
        while(n != 1)
        {
            ll t = p[n];
            while(n % t == 0)
            {
                n = n /t;
            }
            s += t;
        }
        c[i] = s;
    }
}

int main()
{
    seive();
    getfactor();
    prime();
    ll n, m, d, i, e;
    while(cin >> n && n > 0)
    {
        cin >> m;
        d = 0;
        for(i=n; i<=m; i++)
        {
            e = c[i];
            if(s[e] == 0)
                d++;
        }
        cout << d << endl;
    }
    return 0;
}