There is O(sieve) + O(2*2^20) preparation (CPU/RAM) + N*O(20) per query algo for arbitrary numbers, not just primes. Use a heap-alike array where left edge corresponds to setting bit 0 (from highest to lowest) and right corresponds to settings bit 1. Internal nodes tell if you will eventually find prime (or anything else) on that way.
