Sieve of Eratosthenes to solve a Leetcode problem

Problem: https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/

Given two integers L and R, find the count of numbers in the range [L, R] (inclusive) having a prime number of set bits in their binary representation.

(Recall that the number of set bits an integer has is the number of 1s present when written in binary. For example, 21 written in binary is 10101 which has 3 set bits. Also, 1 is not a prime.)

Example 1:

Input: L = 6, R = 10
Output: 4
Explanation:
6 -> 110 (2 set bits, 2 is prime)
7 -> 111 (3 set bits, 3 is prime)
9 -> 1001 (2 set bits , 2 is prime)
10->1010 (2 set bits , 2 is prime)

Example 2:

Input: L = 10, R = 15
Output: 5
Explanation:
10 -> 1010 (2 set bits, 2 is prime)
11 -> 1011 (3 set bits, 3 is prime)
12 -> 1100 (2 set bits, 2 is prime)
13 -> 1101 (3 set bits, 3 is prime)
14 -> 1110 (3 set bits, 3 is prime)
15 -> 1111 (4 set bits, 4 is not prime)

Note:

1. L, R will be integers L <= R in the range [1, 10^6].
2. R - L will be at most 10000.

My first solution used Miller-Rabin to do the primality test. Even being super fast, doing that test for every single input leads to a timeout. Solution was to use the Sieve of Eratosthenes, cache the non-primes in a static variable, and use that cache during the checks. That solution worked but it was still very inefficient albeit passing the bar for leetcode. An improvement (which I have not implemented yet) would be to store the cumulative number of primes from 1..N, and then just use cumulative[b] - cumulative[a-1], caching all the solutions. Cheers, Marcelo

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace LeetCode
{
 class Program
 {
  static void Main(string[] args)
  {
   Solution sol = new Solution();
   Console.WriteLine(sol.CountPrimeSetBits(Int32.Parse(args[0]), Int32.Parse(args[1])));
  }
 }

 public class Solution
 {
  private static Hashtable notPrimes = null;
  public int CountPrimeSetBits(int L, int R)
  {
   if (Solution.notPrimes == null)
   {
    Solution.notPrimes = new Hashtable();
    Solution.notPrimes.Add(1, true);
    int N = 1000000;
    for (int i = 2; i <= (int)(Math.Sqrt(N) + 1); i++)
    {
     for (int j = i; i * j <= N; j++)
     {
      if (!Solution.notPrimes.ContainsKey(i * j)) Solution.notPrimes.Add(i * j, true);
     }
    }

   }

   int total = 0;

   for (int i = L; i <= R; i++)
   {
    int temp = i;
    int count = 0;
    while (temp > 0)
    {
     count += (temp % 2);
     temp /= 2;
    }
    total = !Solution.notPrimes.ContainsKey(count) ? total + 1 : total;
   }

   return total;
  }

  private bool IsPrimeMillerRabin(BigInteger n)
  {
   //It does not work well for smaller numbers, hence this check
   int SMALL_NUMBER = 1000;

   if (n <= SMALL_NUMBER)
   {
    return IsPrime(n);
   }

   int MAX_WITNESS = 500;
   for (long i = 2; i <= MAX_WITNESS; i++)
   {
    if (IsPrime(i) && Witness(i, n) == 1)
    {
     return false;
    }
   }

   return true;
  }

  private BigInteger SqRtN(BigInteger N)
  {
   /*++
             *  Using Newton Raphson method we calculate the
             *  square root (N/g + g)/2
             */
   BigInteger rootN = N;
   int count = 0;
   int bitLength = 1;
   while (rootN / 2 != 0)
   {
    rootN /= 2;
    bitLength++;
   }
   bitLength = (bitLength + 1) / 2;
   rootN = N >> bitLength;

   BigInteger lastRoot = BigInteger.Zero;
   do
   {
    if (lastRoot > rootN)
    {
     if (count++ > 1000)                   // Work around for the bug where it gets into an infinite loop
     {
      return rootN;
     }
    }
    lastRoot = rootN;
    rootN = (BigInteger.Divide(N, rootN) + rootN) >> 1;
   }
   while (!((rootN ^ lastRoot).ToString() == "0"));
   return rootN;
  }

  private bool IsPrime(BigInteger n)
  {
   if (n <= 1)
   {
    return false;
   }

   if (n == 2)
   {
    return true;
   }

   if (n % 2 == 0)
   {
    return false;
   }

   for (int i = 3; i <= SqRtN(n) + 1; i += 2)
   {
    if (n % i == 0)
    {
     return false;
    }
   }
   return true;
  }

  private int Witness(long a, BigInteger n)
  {
   BigInteger t, u;
   BigInteger prev, curr = 0;
   BigInteger i;
   BigInteger lln = n;

   u = n / 2;
   t = 1;
   while (u % 2 == 0)
   {
    u /= 2;
    t++;
   }

   prev = BigInteger.ModPow(a, u, n);
   for (i = 1; i <= t; i++)
   {
    curr = BigInteger.ModPow(prev, 2, lln);
    if ((curr == 1) && (prev != 1) && (prev != lln - 1)) return 1;
    prev = curr;
   }
   if (curr != 1) return 1;
   return 0;
  }

 }
}