Skip to content

Instantly share code, notes, and snippets.

@gnarmis
gnarmis / gist:1050563
Created June 28, 2011 05:43
Finding the Largest Prime Factor of a Composite Number
def maxPrimeFactor(n) #=> maxPrimeFactor(600851475143) => 6857 in 2007.562 ms
# limit the ridiculous range safely
range = n**(1/Math.sqrt(n.to_s.length).floor.to_f)
ary = (1..range).to_a
# Sieve of Eratosthenes (replace with Sieve of Atkin?)
for i in ary
for j in ary
if i != j
if (j % i == 0)
ary.delete(j)
ruby-1.9.2-p180 :004 > def cat.has_nine_lives?
ruby-1.9.2-p180 :005?> true
ruby-1.9.2-p180 :006?> end
=> nil
ruby-1.9.2-p180 :007 > cat.has_nine_lives?
=> true
ruby-1.9.2-p180 :001 > cat = Object.new
=> #<Object:0x0000010085bc58>
ruby-1.9.2-p180 :002 > puts cat.methods.sort
!
!=
!~
<=>
==
===
=~