10539.cpp

/*
   math > number theory > prime numbers > sieve of eratosthenes
   difficulty: medium
   date: 18/Mar/2020
   problem: compute the quantity of non-prime numbers in [lo .. hi] which are divisible by only a single prime number, 0 < lo <= hi < 10^12
   hint: generate all powers of each prime number
   by: @brpapa
*/
#include <iostream>
#include <vector>
#include <bitset>
#define ll long long
#define UB 1000100 // sqrt(10^12)
using namespace std;

vector<ll> primes;
bitset<UB+1> is;

void sieve() {
   primes.clear();
   is.set(); is[0] = is[1] = false;

   for (ll i = 2; i <= UB; i++)
      if (is[i]) {
         primes.push_back(i);
         for (ll j = i*i; j <= UB; j += i) is[j] = false;
      }
}

int main() {
   sieve();

   int T; cin >> T;
   while (T--) {
      ll lo, hi; cin >> lo >> hi;

      ll ans = 0;

      // para cada primo p em [0 .. sqrt(hi)]
      for (ll p : primes) {
         if (p*p > hi) break;

         // para cada potência de p, totalizando O(logp(hi)) iterações
         for (ll j = p*p; j <= hi; j *= p) {
            if (j >= lo) ans++;
         }
      }

      cout << ans << endl;
   }
   return 0;
}