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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| puts "Enter a starting number for your range" | |
| range_begin = gets.chomp.to_i | |
| puts "Enter the ending number for your range" | |
| range_end = gets.chomp.to_i | |
| range = (range_begin..range_end) | |
| dirty_prime_list = [] | |
| range.each do |x| | |
| euler = x**2 + x + 41 | |
| puts euler | |
| dirty_prime_list.push(euler) | |
| end | |
| puts "Here's your list of potential primes:" | |
| #puts dirty_prime_list.to_s | |
| puts "Saving result to output file 'dirty_list.out'" | |
| fh = File.new("dirty_list.out", "w") | |
| fh.puts dirty_prime_list | |
| fh.close |
Hubs by
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