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?

because its looping a through a whole lot of numbers. its going to take time to finish. the purpose of `Project Euler` was to come up with efficient algorithms. — ptierno, Jan 16 '15 at 00:33
Another issue is that Ruby's implementation of `Prime` is slow. Apart from that, yes, the point is to learn algorithms as opposed to solving by brute force. — Charles Caldwell, Jan 16 '15 at 01:22
Or just… [Write In C](https://www.youtube.com/watch?v=1S1fISh-pag) — The Paramagnetic Croissant, Jan 17 '15 at 10:50

score 0 · Answer 1 · edited May 23 '17 at 12:17

I'll address not so much the answer, but how YOU can pursue the answer.

The most elegant troubleshooting approach is to use a debugger to get insight as to what is actually happening: How do I debug Ruby scripts?

That said, I rarely use a debugger -- I just stick in puts here and there to see what's going on.

Start with adding puts "testing #{i}" as the first line inside the loop. While the screen I/O will be a million times slower than a silent calculation, it will at least give you confidence that it's doing what you think it's doing, and perhaps some insight into how long the whole problem will take. Or it may reveal an error, such as the counter not changing, incrementing in the wrong direction, overshooting the break conditional, etc. Basic sanity check stuff.

If that doesn't set off a lightbulb, go deeper and puts inside the if statement. No revelations yet? Next puts inside is_prime(), then inside is_prime()'s loop. You get the idea.

Also, there's no reason in the world to start with 600851475143 during development! 17, 51, 100 and 1024 will work just as well. (And don't forget edge cases like 0, 1, 2, -1 and such, just for fun.) These will all complete before your finger is off the enter key -- or demonstrate that your algorithm truly never returns and send you back to the drawing board.

Use these two approaches and I'm sure you'll find your answers in a minute or two. Good luck!

600851475143 is the actual number in the problem. It's not about factorization in general, but for this specific number. The algorithm used would work fine for 1024, I believe. — Will Ness, Jan 16 '15 at 17:38
I'd recommend going ahead and testing it for smaller number like 1024 as you prove and refine your algorithm. If it takes an hour or a day or a month to solve for the problem you need to solve, it will take a second to solve for a little answer. If you can get that down to 0.5, then 0.1, then 0.001 seconds for a little number through many iterations of tests an optimizations...then the problem you really need to solve might only take a second or a minute or an hour. Use a profiler (ruby-prof, GC:Profiler, etc.) so you can really see where CPU is, and what impact your changes make. — David Hempy, Jan 19 '15 at 02:37
for run time projections, I usually use http://en.wikipedia.org/wiki/Analysis_of_algorithms#Empirical_orders_of_growth methodology. — Will Ness, Jan 19 '15 at 02:40

score 0 · Accepted Answer · edited May 23 '17 at 12:17

"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.

score 0 · Answer 3 · answered Apr 01 '15 at 13:03

0

Do you know you can solve this with one line of code in Ruby?

Prime.prime_division(600851475143).flatten.max

=> 6857

answered Apr 01 '15 at 13:03

Chris Yeung

2,613
6
34
57

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

3 Answers3