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 hidden or 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