3

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)

Abdurakhmon
  • 2,813
  • 5
  • 20
  • 41

3 Answers3

1

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:

Spektre
  • 49,595
  • 11
  • 110
  • 380
  • Actually that is what I am saying you cannot do it unless you have precomputed the numbers – Abdurakhmon Jun 11 '18 at 08:35
  • Why are you creating array of 10,001 and not 10,000 – Abdurakhmon Jun 11 '18 at 08:37
  • @watchit yes ... but this is the only way I know of that is `O(1)` having the primes list is not enough that would need a loop as you correctly assumed. `10000` numbers is not that much and can be hardcoded. There are also files with all 32bit primes in it ~700MByte for such purposes. – Spektre Jun 11 '18 at 08:38
  • @watchit because 0 is also number ... if you do not use it you might tweak this a bit by testing `x-1` then the array would be `[10000]` – Spektre Jun 11 '18 at 08:38
  • With a bit of TMP magic, you could compute it during _compile_ time rather than runtime and pretend you are not really computing it when program runs, so it is O(1) ;) – Artur Biesiadowski Jun 11 '18 at 08:43
  • @ArturBiesiadowski `10000` is really small the computation time would not bee to big. The example I linked has this performance on my setup: `[ 129.846 ms] --- first 664579 primes init up to 9999991` which includes the list constructions and stuff around it so the `SoE` is just a part of that time. So no need to schedule it to background or amortize it or hide it – Spektre Jun 11 '18 at 08:46
  • Process even numbers separately and the sieve array can be reduced to 5,000 bits. – rossum Jun 11 '18 at 10:59
  • @rossum as the answer stated too (only the odd numbers are stored ...) I was hoping it was clear enough – Spektre Jun 11 '18 at 11:24
1

YES!, You can use Sieve of Eratosthenes to check if number is a prime or not, However you will have to precompute for certain number of value and store it in the array and for each query you can check in O(1).

If you do not want to precompute as it will take O(log(long)) time , then you can use this Concept ,

if P is a Prime Number , then P^2 - 1 is divisible by 24. So in case of C++ , if the given number is less than or equal to 10^9 , we can use this concept.

The Source to this Concept can be learned at www.brilliant.org

Shubham Shrivastava
  • 11
  • 1
-2

public static boolean prime(int n) {

    if(n%2 == 0)
        return true;
    else if(n%3 == 0)
        return true;
    else if(n%5 == 0)
        return true;
    else if(n%7 == 0)
        return true;

    
    
    return false;
}
Shambuling Patil
  • 1