Euler Project in Ruby - Problem 3

euler3.rb

# We make array of prime numbers with modulus 0 as long as product_sum < n
 
def prime? n
  (2..(n-1)).each { |x| return false if n % x == 0 }
  true
end
 
n = 600_851_475_143
a = []
product_sum = 1
x = 2 # 2 is the first prime number
 
while product_sum < n
  if n % x == 0 && prime?(x) 
    a << x
    product_sum *= x
  end
  x += 1
end
 
puts "The answer is #{a.last}"

This code doesn't work if there are prime factors that are the same. If n = 4 (or 8, or 9, or 27...) then your while loop will not exit.

I started working on this yesterday and though I arrived at a solution that worked quickly for numbers up to 7 digits. I cried "uncle" and looked a this solution. Although previous commenter dolomite pointed out a flaw in the posted solution, this solution still helped me to refine my attempt. Here it is:

class PrimeFactorGenerator

def initialize(num)
    @num = num
    @test_factor = 2
    @factor_product = 1 # Will multiply prime factors together until product is original number
end

def greatest_prime_factor(number = @num)
    until @factor_product == @num # Switching to factor_product test cut runtime down for large numbers
        if number % @test_factor == 0 # is it a factor?
                @factor_product *= @test_factor # product of all prime factors found so far
                number = number / @test_factor # Next iteration will seek prime factors of remaining quotient. Need this or blows up
        else
                @test_factor += 1 # Next iteration will test new factor
        end
    end
    @test_factor # last factor identified is largest prime factor
end

def to_s
    @num
end

end
g = PrimeFactorGenerator.new(600851475143)
g.greatest_prime_factor # => 6857

Tested with smaller number that have redundant factors (24 = 2_2_2*3) and works for those too.