Google Miller-Rabin test (tho it's not O(log(n))). Also, there is a blog made by peltorator on a simpler method, but unfortunately it is written in russian. https://telegra.ph/Prostoj-test-na-prostotu-09-25

i think the best way is in $$$O(\sqrt n)$$$ which is easy and pretty fast (although not as fast as $$$O(log(n))$$$)

You can precompute it for every integer between $$$1$$$ and $$$A$$$ using Sieve of Eratosthenes. I always use normal one that works in $$$O(AlogA)$$$, but there exists a linear one that works in $$$O(A)$$$

If you only want to see for one number $$$n$$$ if it is prime you can do it in $$$O(\sqrt n)$$$

There is a probabilistic algorithm. The Fermat's last theorem states that if $$$p$$$ is a prime and $$$a$$$ is a natural number that is not divisible by $$$p$$$, then $$$p$$$ divides $$$a^p - a$$$. It doesn't hold in the opposite direction all the time but most of the time. So if you have some natural number $$$p$$$, just check the condition $$$p$$$ divides $$$a^p - a$$$ for many different a and if all of them hold you are very likely to have a prime number. Time complexity is $$$O(k \log n)$$$ with fast exponentiation where $$$k$$$ is the number of different $$$a$$$ you try. If implemented carefully and correctly you can have an algorithm that is correct practically 100% of the time.

The fastest primality test currently is AKS, in 6th power of the logarithm. Essentially making it polynomial in bit size, hence making PRIMES a part of P.