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:
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:
1 comments:
-- 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)).
Post a Comment