Project Euler Problem 3

problem3.rb

# This needs to be reworked. It provides the correct answer, but it is not elegant or efficient.
# On my list to rework later.

def get_prime_factors(number)
  prime_array = sieve_upto(1000000) # hack ... generate prime numbers below 1000000

  prime_array.each do | i |
    if number % i == 0 then
      print i.to_s + " "
    end
  end
end

# copied implementation from internet
def sieve_upto(top)
  print "Generating primes..."
  sieve = []
  for i in 2 .. top
    sieve[i] = i
  end
  for i in 2 .. Math.sqrt(top)
    next unless sieve[i]
    (i*i).step(top, i) do |j|
      sieve[j] = nil
    end
  end
  print " done\n"
  
  sieve.compact
end

get_prime_factors(600851475143)