This blog no longer exists.
You will be redirected to something cool.

Sunday, November 4, 2012

Checking for Primes

I'm writing a script that will check whether or not a number is prime and I'm having some issues on how to do this.

If I take a number, lets say 100, and I want to check and see if it's prime I could do this:
-Divide it by all numbers 2..99 to see whether or not 100 is divisible by them. If not, it passes (it's prime.)
-Check whether it's divisible by 2. If so, it fails (composite.) If its not di

visible, truncate the result of dividing by 2 and check all numbers 2..the_result of dividing by two. This would significantly reduce the pool of numbers I would have to check, BUT I run into another issue...

If I choose to check whether it's divisible by 2, then, if it's not, move onto 3... and THEN if its not divisible by 3, I could really bring the size of the pool of numbers down to ~1/3rd of its original size...

However, when do I stop? At the 1/4 size? 1/8 size?

Optimally, I'd like to do as few operations as possible.

The code that produces the array is as follows:


-- However, when do I stop? At the 1/4 size? 1/8 size? --

You should stop at sqrt(number). In practice it is better to use ceil(sqrt(number)).

This is fine if you only want to find out if a particular number is prime. If you want a whole list, you are better off with erathotenes' sieve. Even with the sieve, you stop iterating after reaching ceil(sqrt(number)).