Expert.
Put your skills to the test.

Problem summary

For each query [a,b], count the prime integers in that inclusive interval. Endpoints can be large, but the total interval lengths are bounded.

Constraints

1 ≤ Q ≤ 1000; 1 ≤ a ≤ b ≤ 1000000000000; sum of inclusive interval lengths ≤ 10000000.

Worked example

Official statement example.

3
1 10
11 20
20 30

4
4
2

Solution analysis

1. Every composite number at most 10¹² has a prime divisor at most 10⁶. Generate these base primes once using the ordinary sieve of Eratosthenes.
2. For a query allocate a boolean array for [a,b]. For each prime p with p²≤b, cross out multiples starting at max(p², ceil(a/p)·p). Starting at p² avoids crossing out p itself. Explicitly cross out 1 if present.
3. In [20,30], crossing out multiples of 2,3 and 5 leaves only 23 and 29. Work is proportional to the short queried intervals plus scanning the base-prime list, rather than to the absolute endpoint b.

Why it works

Every crossed-out number is composite because its marked multiple is at least p². Every composite in the interval has a prime factor p≤√b and is at least p², so it is crossed out by that prime. After removing 1, the remaining numbers are exactly the primes.

Watch out. Compute p², ceiling division and the first multiple in 64-bit arithmetic. Both interval endpoints are included.

An independently written complete program with standard headers.

// Key idea: Every crossed-out number is composite because its marked multiple is at least p². Every
// composite in the interval has a prime factor p≤√b and is at least p², so it is crossed out by that
// prime.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    const int limit=1000000;
    vector<char>composite(limit+1);
    vector<int>primes;
    for(int p=2;p<=limit;++p){
        if(!composite[p]){
            primes.push_back(p);
            if(1LL*p*p<=limit){
                for(int x=p*p;x<=limit;x+=p){
                    composite[x]=1;
                }
            }
        }
    }
    int queries;
    cin>>queries;
    while(queries--){
        long long a,b;
        cin>>a>>b;
        vector<char>marked(static_cast<size_t>(b-a+1));
        for(int p:primes){
            if(1LL*p*p>b){
                break;
            }
            long long first=max(1LL*p*p,((a+p-1)/p)*p);
            for(long long x=first;x<=b;x+=p){
                marked[static_cast<size_t>(x-a)]=1;
            }
        }
        if(a==1){
            marked[0]=1;
        }
        int answer=0;
        for(char value:marked){
            answer+=!value;
        }
        cout<<answer<<'\n';
    }
}