UVa 10990 - Another New Function Solution

#include <iostream>
#include <vector>
#include <bitset>
#include <cmath>
using namespace std;
vector<int> phi(2000001);
vector<int> prime;
bitset<2000001> p;
void calc(){
    int tmp=sqrt(2e6);
    int tmp2=sqrt(tmp);
    for(int i=2;i<=tmp;i++){
        if(!p[i]){
            prime.push_back(i);
            if(i<=tmp2)
                for(int j=i*i;j<=tmp;j+=i)
                    p[j]=1;
        }

    }
}
int main(){
    calc();
    ios::sync_with_stdio(0);
    phi[1]=1;
    for(int i=2;i<=2e6;i++){
        int ans=i,tmp=sqrt(i),n=i;
        for(int j=0;j<prime.size()&&prime[j]<=tmp;j++){
            if(n%prime[j]==0)
                ans-=ans/prime[j];
            while(n%prime[j]==0)
                n/=prime[j];
        }
        if(n>1)
            ans-=ans/n;
        phi[i]=ans;
    }
    phi[2]=1;
    for(int i=3;i<=2e6;i++){
        phi[i]=phi[phi[i]]+1;
    }
    for(int i=2;i<=2e6;i++)
        phi[i]+=phi[i-1];
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>m>>n;
        cout<<phi[n]-phi[m-1]<<endl;
    }
}