I got this question in an interview
Please provide a solution to check if a number is a prime number using a loop of one - O(1). The input number can be between 1 and 10,000 only.
I said that its impossible unless if you have stored all prime numbers up to 10,000. Now I am not entirely sure whether my answer was correct. I tried to search for an answer on internet and the best I came up with AKS algorithm with run-time of O((log n)^6)
it is doable using SoE (Sieve of Eratosthenes). Its result is an array of bools usually encoded as single bit in BYTE/WORD/DWORD array for better density of storage. Also usually only the odd numbers are stored as the even except 2 are all not primes. Usually true value means it is not prime....
So the naive O(1) C++ code for checking x would look like:
bool SoE[10001]; // precomputed sieve array
int x = 27; // any x <0,10000>
bool x_is_prime = !SoE[x];
if the SoE is encoded as 8 bit BYTE array you need to tweak the access a bit:
BYTE SoE[1251]; // precomputed sieve array ceil(10001/8)
int x = 27; // any x <0,10000>
BYTE x_is_prime = SoE[x>>3]^(1<<(x&7));
of coarse constructing SoE is not O(1) !!! Here an example heavily using it to speedup mine IsPrime function: