Skip to content

Instantly share code, notes, and snippets.

@hunj
Last active June 15, 2016 04:17
Show Gist options
  • Save hunj/358eea4298f68d8144cba8328e24286a to your computer and use it in GitHub Desktop.
Save hunj/358eea4298f68d8144cba8328e24286a to your computer and use it in GitHub Desktop.
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"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment