Triprime - 47p

#include <fstream>
using namespace std;

ifstream cin("triprime.in");
ofstream cout("triprime.out");

#define MAX_B 65000000
bool v[MAX_B+1];
#define MAX_P 3940554
long long prim[MAX_P];

int calcnrp(int b){
    int j,i,prime;
    for(j=4;j<=b/6;j+=2){
        v[j]=1;
    }
    for(i=3;i*i<=b/6;i+=2){
        if(v[i]==0){
            for(j=i*i;j<=b/6;j+=i){
                v[j]=1;
            }
        }
    }
    prim[0]=2;
    prime=1;
    for(i=3;i<=b/6;i+=2){
        if(v[i]==0){
            prim[prime]=i;
            prime++;
        }
    }
    return prime;
}

long long tr_pn_k(int x,int prime){
    int i,j,k;
    long long cnt;
    cnt=0;
    for(i=0;i<prime-2;i++){
        j=i+1;
        k=i+2;
        while(prim[i]*prim[j]*prim[k]<=x && k<prime)
            k++;
        k--;
        cnt+=(k-j);
        j++;
        while(j<k){
            while(prim[i]*prim[j]*prim[k]>x)
                k--;
            if(j<k)
                cnt+=(k-j);
            j++;
        }
    }
    return cnt;
}

int main()
{
    long long a,b,prime;
    cin>>a>>b;
    prime=calcnrp(b);
    cout<<tr_pn_k(b,prime)-tr_pn_k(a-1,prime);
    return 0;
}