N + NOD (N)

#include<bits/stdc++.h>
#define MAX 1000005

using namespace std;

vector<int>prime;

vector<int>sequence;

int NOD[MAX],vis[MAX];

bool check[MAX];

void sieve()
{
    int i,j,k;

    k = sqrt(MAX);

    prime.push_back(2);

    for(i=3; i<=k; i+=2)
    {
        if(check[i]==0)
        {
            for(j=i*i; j<MAX; j+=i+i)
            {
                check[j]=1;
            }
        }
    }

    for(i=3;i<MAX;i+=2)
    {
        if(check[i]==false)
        {
            prime.push_back(i);
        }
    }

    return ;
}

int countDivisor(int n)
{
    int cnt = 1,divisor = 1,i;

    for(i=0; prime[i]*prime[i]<=n; i++)
    {
        if(n%prime[i]==0)
        {
            cnt = 1;

            while(n%prime[i]==0)
            {
                n/=prime[i];

                cnt++;
            }

            divisor*=cnt;
        }
    }

    if(n!=1)
    {
        divisor*=2;
    }

    return divisor;
}

void solve()
{
    int i;

    NOD[1] = 1;

    for(i=2; i<MAX; i++)
    {
        NOD[i] = countDivisor(i);
    }

    sequence.push_back(1);

    vis[1] = 1;

    while(sequence.back()<=1000000)
    {
        sequence.push_back(sequence.back()+NOD[sequence.back()]);

        vis[sequence.back()] = 1;
    }

    for(i=1; i<MAX; i++)
    {
        vis[i]+=vis[i-1];
    }

    return ;
}

int main()
{
    sieve();

    solve();

    int n,test,i,j,tc,L,R,l,h;

    scanf("%d",&test);

    for(tc = 1; tc<=test; tc++)
    {
        scanf("%d%d",&L,&R);

        printf("Case %d: %d\n",tc,vis[R]-vis[L-1]);
    }

    return 0;
}