*One speedy way is to use the Sieve of Eratosthenes.*

It's speedy if you want all primes below a certain number, or if you need to determine primality of "a lot of" numbers, but it isn't for checking a single number.

Checking all the possible divisors can be done in `O(√N)` (throw in a factor of `O(log n)` to do the division if you have really big numbers). However, just initializing the sieve will take you `Ω(N)` time. And then you still have to do the work: `Ω(N/p`_{i}) for the `i`^{th} prime.

The fastest way is probably just to use bigprimes.net, which has the first 1.4 billion primes on file.

Comment onRe^2: is it prime?