Uva 10539 - Almost Prime Numbers Solution

Problem Link : 10539 - Almost Prime Numbers 

Solution in C++: 

///La ilaha illellahu muhammadur rasulullah

///******Bismillahir-Rahmanir-Rahim******///

///Abul Hasnat  Tonmoy

///Department of CSE,23rd batch

///Islamic University,Bangladesh

///**********ALLAH IS ALMIGHTY************///

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define mx 10000009

ll prime[mx],i,j;

void sieve()

{

    memset(prime,true, sizeof(prime));

    for(ll i = 4; i <mx; i += 2)

    {

        prime[i] = false;

    }

    prime[0] = prime[1] = false;

    for(ll i = 3; i * i < mx; i+=2)

    {

        if(prime[i])

        {

            for(ll j = i * i; j < mx; j += (2 * i))

            {

                prime[j] = false;

            }

        }

    }

}

vector<ll>v;

void preCal()

{

    for(ll i = 2; i < mx; i++)

    {

        if(prime[i])

        {

            for(ll j = i * i; j <= 1000000000000; j*=i)

            {

                v.push_back(j);

            }

        }

    }

    sort(v.begin(),v.end());

}

int main()

{

    sieve();

    preCal();

     ll t,a,b,x,y,r;

     cin>>t;

    while(t--)

    {

        cin>>a>>b;

        x=lower_bound(v.begin(),v.end(),a)-v.begin();

        y=lower_bound(v.begin(),v.end(),b)-v.begin();

        cout<<y-x<<endl;

    }

}