{{ message }}

Instantly share code, notes, and snippets.

# hunj/euler_003.rb

Last active Jun 15, 2016
Project Euler #003 solution, comparing with square root
 require 'benchmark' the_number = 600_851_475_143 # monkeypatching class Fixnum def prime? # O(n) (2..(self - 1)).each do |divisor| return false if self % divisor == 0 end true end def prime_sqrt? # O(n) (2..Math.sqrt(self).to_i).each do |divisor| return false if self % divisor == 0 end true end def factors result = self divisors = [] # O(n) (1..self).each do |divisor| break if result == 1 if result % divisor == 0 result /= divisor divisors << divisor end end divisors end def factors_sqrt result = self divisors = [] # O(n) (1..Math.sqrt(self)).each do |divisor| break if result == 1 if result % divisor == 0 result /= divisor divisors << divisor end end divisors end def prime_factors factors.select { |number| number.prime? } end def prime_factors_sqrt factors_sqrt.select { |number| number.prime? } end end time = Benchmark.realtime do the_number.prime_factors.last end puts "Original:\t#{time*1000} milliseconds" time_sqrt = Benchmark.realtime do the_number.prime_factors_sqrt.last end puts "Math.sqrt:\t#{time_sqrt*1000} milliseconds"