OJ Board

Could anybody tell me if there's a method which checks if the number n is a prime? I know only an algo O(sqrt(n)) which is well-know. There's Eratostenes' Sieve too, but the big numbers cannot be checked due to memory limits.

You can also check out the BigInteger source code in Java's API. They have various implementation in there.