in reply to Re: is it prime?

in thread is it prime?

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.One speedy way is to use the Sieve of Eratosthenes.

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`prime.

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

In Section
Seekers of Perl Wisdom