Project Euler #3 Ruby Solution - What is wrong with my code?

Question

This is my code:

def is_prime(i)
    j = 2
    while j < i do 
        if i % j == 0
            return false
        end
        j += 1
    end
true
end

i = (600851475143 / 2)
while i >= 0 do 
    if (600851475143 % i == 0) && (is_prime(i) == true) 
        largest_prime = i
        break 
    end
    i -= 1
end



puts largest_prime

Why is it not returning anything? Is it too large of a calculation going through all the numbers? Is there a simple way of doing it without utilizing the Ruby prime library(defeats the purpose)?

All the solutions I found online were too advanced for me, does anyone have a solution that a beginner would be able to understand?

Answer 1

"premature optimization is (the root of all) evil". :)

Here you go right away for the (1) biggest, (2) prime, factor. How about finding all the factors, prime or not, and then taking the last (biggest) of them that is prime. When we solve that, we can start optimizing it.

A factor a of a number n is such that there exists some b (we assume a <= b to avoid duplication) that a * b = n. But that means that for a <= b it will also be a*a <= a*b == n.

So, for each b = n/2, n/2-1, ... the potential corresponding factor is known automatically as a = n / b, there's no need to test a for divisibility at all ... and perhaps you can figure out which of as don't have to be tested for primality as well.

Lastly, if p is the smallest prime factor of n, then the prime factors of n are p and all the prime factors of n / p. Right?

Now you can complete the task.

update: you can find more discussion and a pseudocode of sorts here. Also, search for "600851475143" here on Stack Overflow.