1

I am trying to find the largest prime value of a big number, but it takes far too long. For example, to find the largest prime of 999999999, it takes about 55 seconds. How can I improve this?

require 'prime'

def highestprime num

  i = 1
  counter = 0
  count = -1
  factors = []
  primes = []

  while (i < num/2) #checks for all factors of number
    i += 1
    if (num%i == 0)
      factors.push(i) #adds all factors to the end factors array
    end
  end

  while (counter != factors.length) #goes through whole array
    counter += 1
    count += 1
    if (factors[count].prime?)
      primes.push factors[count]
    else
      next
    end
  end
  puts primes.pop
end
RubyUser
  • 29
  • 7

2 Answers2

3

This is the first thing I'd look at:

while (i < num/2)

You only need to go up to the square root of a number to work out all its factors. Pseudo-code would be something like:

factors = []
i = 1
while i * i <= num:
    if num % i == 0:
        factors.push(i)
        factors.push(num/i)
    i++

(assuming you still want to do it that way - see below).

However, there's absolutely no need to store all these factors then look for the highest prime.

Since you're finding the factors in ascending order, you can also find them at the same time in descending order, using the "trick" in that second factors.push() call above - if i is a factor of num, then so is num / i.

So you can use the same loop to exit early if the prime factor is above the square root (because those are being found in descending order, the first one found is the highest).

Otherwise keep going until you reach the square root and get the highest found to date (you need the last one in that case since you're searching in ascending order).

The code for this would be something like:

require 'prime'

def highestprime num
    i = 1
    large = -1
    while (i * i <= num)
        if (num % i == 0)
            if ((num / i).prime?)
                return num / i
            end
            if (i.prime?)
                large = i
            end
        end
        i = i + 1
    end
    return large
end

puts highestprime 999999999

which returns the result 333667 in well under a second:

pax$ time ruby testprog.rb
333667

real    0m0.160s
user    0m0.031s
sys     0m0.124s

That's about 350 times faster than your original 55-second solution, hopefully that'll be fast enough for you :-)

Or even faster if you take out the process startup/shutdown costs with:

require 'benchmark'
Benchmark.bm do |xyzzy|
    xyzzy.report {highestprime 999999999}
end

which gives:

    user     system      total        real
0.000000   0.000000   0.000000 (  0.000316)
paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
  • Amazing! Just one question, why is `long = -1`? Did you just select an arbitrary value? – RubyUser Mar 24 '15 at 02:30
  • @RubyUser, assuming you mean `large` rather than `long`, yes, I wanted to select an arbitrary value that couldn't normally be returned by the code (since all numbers being checked are positive). In other words, it's a sentinel value meaning no solution was found. – paxdiablo Mar 24 '15 at 02:33
  • Yes, sorry, that's what I meant. Thanks. – RubyUser Mar 24 '15 at 02:36
3

How about:

require 'prime'
999999999.prime_division.last.first #=> 333667

require 'benchmark'
Benchmark.bm do |x|
  x.report {999999999.prime_division.last.first}
end
    user     system      total        real
0.000000   0.000000   0.000000 (  0.000088)
Cary Swoveland
  • 106,649
  • 6
  • 63
  • 100
  • Wow, I didn't know about those methods. – RubyUser Mar 24 '15 at 02:28
  • 2
    If the reader is puzzled by @Amadan's comment (which is now gone!), let me explain. He posted exactly the same solution as mine just a few seconds after I posted. Seeing my answer, deleted his. I contacted him by commented on his answer to another question, suggesting he reinstate his answer, as it was a tie. His comment basically said one answer is enough. – Cary Swoveland Mar 24 '15 at 02:31