In my continuing quest to expand my knowledge of all things Computer Science, I stumbled across the Generator topic on Wikipedia. I ended up here after reading an excerpt from Python Cookbook.
The Wikipedia article describes a generator as something that looks like a function but behaves like an iterator. The interesting thing to me is that they can be used to build endless lists.
For example, the Python Cookbook gives several generators that will list all prime numbers (given enough time). The Wikipedia article gives another way of generating prime numbers.
I was surprised that Ruby wasn’t mentioned in the Wikipedia article so I set off on a search for information about Ruby generators. Unfortunately, most of what I found was dealing with code generators for Rails which is something else entirely.
The Ruby Documentation contains a description of the Generator class with a brief example. I was able to use this to convert Wikipedia’s simple prime number generator to Ruby.
require 'generator'
g = Generator.new do |g|
n = 2
p = []
while true
if p.all? { |f| n % f != 0 }
g.yield n
p << n
end
n += 1
end
end
Using this code, each time you call g.next it will return the next prime number starting with 2. For example, this will print the first 25 prime numbers:
for i in 1..25
puts g.next
end
If you examine the source code in both Python and Ruby you’ll find that they are remarkably similar. The only change is basically replacing Python’s any function with a call to Ruby’s Enumerable#all?.
The more I learn about Python and Ruby, the more similar I realize they are. I have yet to find anything in Python that can’t be done just as easily in Ruby or vice-versa.
Thanks. Today it was very useful during the Python vs Ruby “holy war” on one russian programmers forum! 😉
Just to note, there are not a finite number of primes. 🙂
Prove it 🙂
Love this. I was hunting for the exact solution to chain more than one “filter” on a large list. Perfect fit for me.
Checkout fibers, too, I suppose 🙂
-r
If you’re after code similarity, you can use Enumerable#any? instead of Enumerable#all?:
if p.any? { |f| n % f == 0 }
or
if p.any? { |f| (n % f).zero? }
(IMHO using positive checks like the above is also simpler to read and parse by humans).
Montana says “there are not a finite number of primes.”
Anthony says “Prove it”
Assume there are a finite number of primes. If you multiply them all together, you will have a number for which every prime is a multiple. Add one to this number, and you will have a new number which no prime divides. Hence this new number is prime. This is a contradiction, since it is not in the finite set of all primes, so the assumption is wrong and there are an infinite number of primes.
Or, in haiku http://xkcd.com/622/
The above proof is nearly complete. Instead of “Hence this number is prime…” it should say “This number is prime or composite. If it’s prime, that’s a contraction; QED. If it’s composite, it can be factored into primes, none of which we previously knew about; contradiction; QED.”
In short, given any finite list of primes, it’s always possible to find a new one. Therefore the list is infinite. This proof goes back to Euclid’s time.
The fundamental assumption behind these “proofs’ is that contradictions cannot co-exist. However that may not be true in the realm of infinity. Philosophically this is a FAIL.
The proof given by Joshua is correct and well known, Gavin’s addition is not needed.
The proof is valid. Ah, why argue such things on a web forum? I must be crazy.
It is possible to come up with arguments, statements and predicates that are self-contradictory or ill defined, such as the riddle about “who shaves the barber?” (google it) and the corresponding attack on set theory… Such are neither true nor false, and could be used to create a confusing, false proof.
This is not specifically to do with infinite series, or set theory, as the “barber paradox” illustrates. This particular proof about prime numbers is well known, and you won’t find a sane and educated mathematician to doubt it!
I can not resist ….
@Infinite proof says :
“The fundamental assumption behind these “proofs’ is that contradictions cannot co-exist. However that may not be true in the realm of infinity. Philosophically this is a FAIL.”
prove it 😉