CODEWITHSUNDEEP
ruby
Steven Harlow
Steven Harlow

Reputation: 651

Project Euler #3 in Ruby solution times out

I'm going through a few of the Project Euler problems to practice problem solving using Ruby. I came up with the following solution for problem 3, and while it works for smaller numbers, it never seems to return a value for larger numbers. Is this because of something to do with Bignum? Can someone describe to me why it's timing out, and better way to solve this problem (preferably with reasoning/info on what's going on behind the scenes. I'm trying to understand)

Project Euler problem:

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

My solution:

def primecheck(number)
  (2...number).each { |x| return false if number % x == 0}
  true
end

def largestprime(number1)
  factors = []
    (1..number1).each do |i|
      if number1 % i == 0 && primecheck(i)
        factors << i
      end
    end
puts "The answer is #{factors.last}"
end

largestprime(600_851_475_143)

Upvotes: 1

Views: 1791

Answers (2)

hammar
hammar

Reputation: 139860

Hint: Once you've found a prime factor, you can divide by it. This greatly reduces the range of remaining potential divisors you have to check.

Using your first example:

13195/5 = 2639,
2639/7  = 377,
377/13  = 29,
29/29   = 1, done.

This way, we only had to check up to 29 instead of all the way to 13195.

There are ways to improve it further, but this optimization alone should be more than enough for this simple problem.

Upvotes: 10

arbitUser1401
arbitUser1401

Reputation: 575

It is going through all the numbers from 1 to 600851475143. And it also checks if number is prime, for all the numbers. So total number of operation is O(n^3/2) which is should be around 10^18. Which is expected to take years for computing that. You should change the algorithm so that asymptotic complexity reduces

Upvotes: 4

Related Questions