UVA10539 Almost prime

uva10539.cpp

/*
** id :template
** author : swap_coder
** time:
*/


#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <cstdlib>
#include <stack>
using namespace std;

#define fi(i,a,b) for(int i=(int)a;i<=(int)b;i++)
#define fd(i,a,b) for(int i=(int)a;i>=(int)b;i--)
#define rep(i,n)  for(int i=0;i<n;i++)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define INF (1<<29)
#define EPS 1e-9
#define PI acos(-1.0)
//stl
 #define sz(a) int((a).size())
 #define pb push_back
 #define all(c) ((c).begin(),(c).end())
 #define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
 #define present(c,x) ((c).find(x) != (c).end())
 #define cpresent(c,x) (find(all(c),x) != (c).end())
 #define pf printf
 #define sf scanf


typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii>    vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef map<string,int> msi;

bool is_prime[1000001];
vi prime;
void sieve()
{
    memset(is_prime,true,sizeof is_prime);
    for(int i=2;i<1000001;i+=2)
        is_prime[i]=false;
    prime.pb(2);
    for(int i=3;i<=1000;i+=2)
    {
        if(is_prime[i])
        {
            for(int j=i;i*j<=1000001;j++)
                is_prime[j*i]=false;
            prime.pb(i);
        }
    }
    for(int i=1001;i<=1000000;i+=2)
    {
        if(is_prime[i])
            prime.pb(i);
    }
}

int main()
{
    sieve();
    vector<ll> almost;
    int nop=sz(prime);
    for(int i=0;i<nop;i++)
    {
        ll j;
        ll k=prime[i];
        for(j=k*k;j<1000000000000;j*=k)
        {
            almost.pb(j);

        }

    }
    //cout<<almost.size()<<endl;
    int t;
    cin>>t;
    ll m,n;
    while(t--)
    {
        cin>>m>>n;
        ll count=0;
        ll noalm=sz(almost);
        for(ll i=0;i<noalm;i++)
            if(almost[i]<=n&&almost[i]>=m)
                count++;
        cout<<count<<endl;
    }
  return 0;
}