https://en.wikipedia.org/wiki/Prime_number_theorem

Prime numbers meets often. You can check that head-on decision (check every a XOR i, i=0,1,2...) uses a few numbers

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.

Edited by author 19.06.2026 17:53