Thursday, August 11, 2011

Project Euler #3 in Ruby

Project Euler #3

The prime factors of 13195 are 5, 7, 13 and 29.  What is the largest prime factor of the number 600851475143?

 Here is my solution in Ruby:


  1. def lPrimeFactor(n)
  2.   i = 2
  3.   largest = 0
  4.   while (i <= n)
  5.     if (n % i == 0)
  6.       while (n % i == 0 )
  7.         n = n / i
  8.         largest = i
  9.         i += 1
  10.       end
  11.     end
  12.     i += 1
  13.   end
  14.   return largest
  15. end
  16. puts lPrimeFactor(600851475143)

This is a great example for defining methods (or functions if you are a 'C' guy or gal).  You will notice in line 1 the 'def lPrimeFactor(n)'.  'def' is the keyword for 'define', as in 'define function'.  Whenever you define a function you also have to end that definition, as you will notice in line 15.  The declaration of our function here to find the largest prime factor is written in camel-case, while the standard is to write it in all lower-case.  You may write it however you like, if you use NetBeans though it might get grumpy at you. 

In explanation of the code I have written here, all it does is check to see if 'i' is a factor of n, if so it will divide it and then continue to do so until it is not (like in the case of 8, it would divide by 2, three times), and then continues on to the next number working its way up until i is smaller than n, keeping track of the factors and returning the last one it divides successfully. Pretty straightforward. 

1 comment: