CODEWITHSUNDEEP
rubyprimesfactors
Sergi
Sergi

Reputation: 501

Biggest prime factor of a number in Ruby

Good morning,

I wrote the following code which works with small-is numbers, to find the biggest prime factor of a number. I can't use Prime and I need to come-up with a manual solution.

def is_prime?(number)
  list = (2..(Math.sqrt(number))).to_a
  list.each do |i|
    return false if number % i == 0 
  end 
  true 
end 

def biggest_prime(number)
  list = (2..((number))).to_a
  divisors = list.select{|i| is_prime?(i)}
  divisors.select{|i| number % i == 0 }.max
end

The prime factors of 13195 are 5, 7, 13 and 29.

biggest_prime(13195) => 29

However when I try with the edge case of biggest_prime(600851475143) the system freezes.

Anybody could tell me how to refactor my code to make it more efficient?

Many thanks!

Upvotes: 1

Views: 975

Answers (4)

kiskimoknut
kiskimoknut

Reputation: 21

When we look at the problem like it should be solved in the paper, we can use prime_division. It gives you a set of prime pairs your number divided by. It works fast with big numbers.

p (Prime.prime_division(number))[-1].max

Upvotes: 2

kitpao
kitpao

Reputation: 1

You can do it by changing the max number dividing it until you have no more prime numbers to divide against. That way you don't care about the intermediate prime numbers and reduce the iterations greatly :)

    def top_prime(n) 
      max = n
      lower = 2

      while lower < max
         while max % lower == 0 && max != lower
           max = max / lower
         end
      lower = lower+1
      end
      max
    end

    puts top_prime(600851475143)

Upvotes: 0

J&#246;rg W Mittag
J&#246;rg W Mittag

Reputation: 369556

There are many problems with your code that make it massively inefficient:

  • In your biggest_prime method, you construct an Array in memory of every number less than your target number, instead of just iterating through the range. For 600851475143, the size of that Array in memory is ~4 TiByte. Do you have 4 TiByte of RAM? If not, your system will create a huge swapfile and be swapping constantly. Use a Range instead! In fact, you are already using a Range, but then convert it to an Array for absolutely no reason at all.
  • The same happens in your is_prime? method. This Array is a lot smaller (only about 6 MiByte at its largest), but you create it over and over and over again, 600 billion times! Creating an Array of n numbers takes O(n) amount of time, so creating an Array of sqrt(n) numbers n times takes O(n * sqrt(n)) time. In total, you need SUM(sqrt(n), n = 1 TO 600851475143) steps, which is about 310498000000000000 steps.
  • That is also the number of steps you need for your entire algorithm. Even if you had a 10 GHz CPU, and this CPU had 100 cores, and your problem were perfectly parallelizable, and you could perform one entire iteration of your algorithm within a single CPU instruction, you would still need 3.5 days to get the result. Since you are not using parallelism, probably don't have a 10 GHz CPU, and an iteration is going to take 10s or hundreds of CPU cycles, a more realistic number would be at least 100 years.

So, what you need to do, is to massively cut down the number of iterations, and the amount of memory.

The latter is easiest: use Ranges instead of Arrays.

The former requires a bit of thinking. Here is one idea: You check the same numbers over and over again. That's not necessary. Once you have determined that a number is a divisor, you already know it is a divisor, you don' need to check it again.

Likewise, you check the same number over and over again for primality. But once you have determined that a number is prime, you don't need to check that again, it's not very likely to change, after all.

But first, let's look at what the most efficient solution would look like:

require 'prime'

def biggest_prime(number)
  number.prime_division.last.first
end

Upvotes: 8

ForeverZer0
ForeverZer0

Reputation: 2496

I would personally just use the built-in functions for this instead of trying to reinvent the wheel.

require 'prime'
number = 13195
Prime.each(number).select { |n| number % n == 0 }

This will result in the expected output of [5, 7, 13, 29]. The last value will always be the largest, so...

Prime.each(number).select { |n| number % n == 0 }.last

Gives the 29 you are looking for. This could obviously be cleaned up a little bit, but gives you the idea.

This "freezes" up with the exact same number, which is likely do to going into a Bignum and out of the 32-bit integer range (actually 31 bits for Ruby). I would have to dig into the C code to see what the freeze is all about, though, or test with some other 64-bit and higher numbers to see if the results are repeatable.

Upvotes: 4

Related Questions