UVA 10539 Almost Prime

Almost prime numbers are the non-prime numbers which are divisible by only a single prime number. In this problem your job is to write a program which finds out the number of almost prime numbers within a certain range.
Input
First line of the input file contains an integer N (N ≤ 600) which indicates how many sets of inputs are there. Each of the next N lines make a single set of input. Each set contains two integer numbers low and high (0 < low ≤ high < 1012).
Output
For each line of input except the first line you should produce one line of output. This line contains a single integer, which indicates how many almost prime numbers are within the range (inclusive) low…high.
Sample Input
3
1 10 1 20 15
Sample Output
3 4 1

题意：
给出范围low~high,问说在这个范围内有多少个数满足n=p^b(p为素数)
思路：
首先打表处理出1e6以内的素数，然后循环素数表中

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;
long long prime[1000001];
int j[1000001];
int cnt=0;
void tab()
{
    int max=1000001;
    for(int i=2;i<max;i++)
    {
        if(j[i]==0)
        {
            prime[cnt++]=i;
            for(int k=i*2;k<max;k+=i)
                j[k]=1;
        }
    }
}
int main()
{
    tab();
    int N,i,sum;
    long long low,high,m;
    cin>>N;
    while(N--)
    {
        sum=0;
        cin>>low>>high;
        for(i=0;i<cnt;i++)
        {
            m=prime[i]*prime[i];
            if(m>high)
                break;
            while(m<=high)
            {
                if(m>=low)
                    sum++;
                m*=prime[i];
            }
        }
        cout<<sum<<endl;
    }


    return 0;
}