0

Best logic for Prime Number ?

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

18th Feb 2022, 5:07 AM
Hritik
1 Answer
+ 4
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
18th Feb 2022, 5:21 AM
Tibor Santa
Tibor Santa - avatar