Jul
16
In my attempt to learn Ruby out in the open, here’s my solution for Project Euler Problem 21.
Though I could have used it to solve other problems, this problems made it obvious that I need to start caching results as they are calculated for quick look up later in the routine. I didn’t do that here, but I need to start working caching techniques into my solutions. I also need to look into the use of (1..10_000).each versus 10_000.times. I will do a few benchmarks to see which performs better. Feel free to spill the beans and spoil the surprise for me.
As always, any feedback is welcome.
# Euler 21
# http://projecteuler.net/index.php?section=problems&id=21
# Let d(n) be defined as the sum of proper divisors of n
# (numbers less than n which divide evenly into n).
# If d(a) = b and d(b) = a, where a != b, then a and b
# are an amicable pair and each of a and b are called
# amicable numbers.
# For example, the proper divisors of 220 are
# 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110;
# therefore d(220) = 284. The proper divisors of
# 284 are 1, 2, 4, 71 and 142; so d(284) = 220.
# Evaluate the sum of all the amicable numbers under 10000.
require 'mathn'
timer_start = Time.now
class Integer
def divisors_sum
n = self
sum = 1
(2..Math.sqrt(n)).each do |i|
sum += n / i + i if n % i == 0
end
sum
end
end
sum = 0
(0..10_000).each do |a|
b = a.divisors_sum
sum += a if (a != b && b.divisors_sum == a)
end
puts sum
puts "Elapsed Time: #{(Time.now - timer_start)*1000} milliseconds"</div>
You might want to check out this stack overflow question on memoization:
http://stackoverflow.com/quest.....y-on-rails
Really nice find, Dave. Maybe premature optimization IS the root of all evil? I think I would benefit from caching in this case, but the link you provided makes we want to do some benchmarking. The routine currently takes 471.027 milliseconds to complete. Way too slow.
Hey
,
you actually don’t need to
require 'mathn', there is also a Math constant for basic things. Furthermore,mathnredefinessqrt, so that the code even runs slower!By the way, another popular Ruby trick to get the square root is:
n**0.5I have been exploring for a little bit for any high quality articles or weblog posts on this sort of space . Exploring in Yahoo I eventually stumbled upon this website. Studying this information So i?¦m happy to express that I’ve an incredibly excellent uncanny feeling I came upon exactly what I needed. I so much without a doubt will make sure to do not fail to remember this web site and provides it a glance regularly.
A person necessarily lend a hand to make severely posts I’d state. That is the first time I frequented your website page and so far? I surprised with the research you made to create this actual submit extraordinary. Wonderful task!
For a Joomla website how do you get the drop down menus to display correctly in Internet Explorer 6?