note
JavaFan
<blockquote><em>One speedy way is to use the Sieve of Eratosthenes.</em></blockquote>
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.
<p>
Checking all the possible divisors can be done in <tt>O(√N)</tt> (throw in a factor of <tt>O(log n)</tt> to do the division if you have really big numbers). However, just initializing the sieve will take you <tt>Ω(N)</tt> time. And then you still have to do the work: <tt>Ω(N/p<sub>i</sub>)</tt> for the <tt>i<sup>th</sup></tt> prime.
<p>
The fastest way is probably just to use bigprimes.net, which has the first 1.4 billion primes on file.
969110
969135