Best logic for Prime Number ?

Question

Is there a way to know if a number is prime or not where time complexity is less then O(logn)

Answer 1

From Wikipedia / Sieve of Eratosthenes:
"The time complexity of calculating all primes below n in the random access machine model is O(n log log n) operations, a direct consequence of the fact that the prime harmonic series asymptotically approaches log log n. It has an exponential time complexity with regard to input size, though, which makes it a pseudo-polynomial algorithm."
https://en.m.wikipedia.org/wiki/Sieve_of_Eratosthenes
This algorithm is the most effective for finding a range of small primes. When dealing with larger numbers and determining their primality, other methods might be more useful like Miller-Rabin.
https://en.m.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test