Topcoder SRM 471 DIV 2, L1 PrimeContainers

// Topcoder PrimeContainers

import java.util.*;

class TopcoderSolution {
    public static void main(String[] args) {
        PrimeContainers obj = new PrimeContainers();
        System.out.println(
                obj.containerSize(47)
                );
    }
}

// change to public before submit
public class PrimeContainers {
    public int containerSize(int N)
    {
        boolean[] primes = GetPrimeTable(1000000);
        int div = 1;
        int cnt = 0;
        while (true) {
            if (N / div == 0)
                break;
            if (primes[N / div])
                cnt++;
            div *= 2;
        }
        return cnt;
    }

    public static boolean[] GetPrimeTable(int maxNum) {
        boolean[] isPrime = new boolean[maxNum + 1];
        for (int i = 0; i < isPrime.length; i++) {
            isPrime[i] = true;
        }
        isPrime[0] = isPrime[1] = false;
        int sqrtMaxNum = (int) Math.sqrt(maxNum) + 1;
        for (int i = 2; i <= sqrtMaxNum; i++) {
            if (!isPrime[i])
                continue;
            int k = i * i;
            while (k <= maxNum) {
                isPrime[k] = false;
                k += i;
            }
        }
        return isPrime;
    }

}