I mean...the naive approach for a prime number check is o(n) which is linear. Probably u've meant constant time?