CODEWITHSUNDEEP
rubyalgorithmprimes
RubyUser
RubyUser

Reputation: 29

Improving algorithm execution time and prime numbers

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

Upvotes: 1

Views: 163

Answers (2)

paxdiablo
paxdiablo

Reputation: 882028

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)

Upvotes: 3

Cary Swoveland
Cary Swoveland

Reputation: 110725

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)

Upvotes: 3

Related Questions