CountPrime

#include <fstream>
#define ULL unsigned long long int
using namespace std;
ULL base[] = {0, 2, 3, 23};

ULL exPow(ULL n,ULL p,ULL mod)
{
  ULL sol = 1, nr = n;
  for(ULL i = 0; (1ULL << i) <= p; i++)
  {
    if((1 << i) & p)
      sol = 1LL * sol * nr % mod;
    nr = 1LL * nr * nr % mod;
  }
  return sol;
}

int rabin_miller(ULL n)
{
  if(n < 2)
    return 0;
  for(int i = 1; i <= 3; i++) {
    if(n == base[i])
      return 1;
  }
  if(n % 2 == 0)
    return 0;
  ULL tmp = n - 1, p2 = 0;
  while(tmp % 2 == 0)
    tmp /= 2, p2++;
  for(int i = 1; i <= 3; i++) {
    ULL ans = exPow(base[i], tmp, n);
    if(ans == 1 || ans == n - 1)
      continue;
    ULL j = 1;
    while(j < p2 && ans != n - 1)
      ans = 1LL * ans * ans % n, j++;
    if(ans != n - 1)
      return 0;
  }
  return 1;
}

int main()
{
    ULL st,dr;
    ifstream f("countprime.in");
    f>>st>>dr;
    ULL c=0;
    for(ULL i=st;i<=dr;++i)
        c+=rabin_miller(i);
    ofstream g("countprime.out");
    g<<c;
    return 0;
}