Last active
June 15, 2016 04:17
-
-
Save hunj/358eea4298f68d8144cba8328e24286a to your computer and use it in GitHub Desktop.
Project Euler #003 solution, comparing with square root
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment