Calculating primes in Ruby

So unless it’s not become apparent from anyone who follows this blog (which is all of about zero people from what I can tell) I am learning ruby by basically attempting to solve Project Euler problems with it. One of the things that you really need in order to succeed here is a good method of calculating primes. Here’s what i came up with (EDIT: I later found this algorithm to be hideously inefficient for calculating many primes at once, so this alone will not get you through all the Euler problems).

I basically wanted to be able to call a method on a Fixnum object that would tell me if it was prime. Before anyone points out, i know this is already built into ruby 1.9.2 πŸ™‚ I wanted to be able to write code like this;

1.prime?
9.prime?
11.prime?

I managed to achieve this using modules;

module MathModule
  
  def prime?  
 		
    return true if self == 2
 		
    return false if self == 0  or self == 1 or self.even?    
    
    3.step(self-1, 2) { |i| return false if self % i == 0 }   
    
    return true
		
  end

end

#This part basically applies the module to the Fixnum class
class Fixnum 
  include MathModule
end

Once i had this, I was able to solve many Euler problems pretty easily by building a helper class. Apologies in advance by the way if I am getting all of this terminology wrong – I don’t have the confidence right now to refer to the above as a “mixin” but I think that’s what it might be. Anyway, here’s some of the helpers that are possible with the above;

class MathHelper

	def self.primesUpTo(num)
		primes = []
		1.step(num,2) { |i| primes << i if i.prime? }
		return primes
	end
	
	def self.firstXPrimes(num)
		primes = []
				
		i = 0
		x = 1
		
		while i < num
			if x.prime?
				primes << x
				i += 1
			end
	  	 x += 2
		end	
		
		return primes
		
	end
	
	def self.nthPrime(num)
		primes = firstXPrimes num
		return primes.last
	end
	
end
Advertisements

3 thoughts on “Calculating primes in Ruby

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s