ruby - 改进算法执行时间和素数

Question

我正试图找到一个大数的最大质数，但它花费的时间太长了。例如，要找到 999999999 的最大素数，大约需要 55 秒。我该如何改进？

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

Answer 1

这是我首先要看的东西:

while (i < num/2)

您只需求一个数的平方根，即可算出它的所有因数。伪代码类似于:

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

(假设您仍想这样做 - 见下文)。

---

但是，绝对没有必要存储所有这些因素然后寻找最高素数。

由于您按升序查找因子，因此您也可以同时按降序查找它们，使用上面第二个 factors.push() 调用中的“技巧” -如果 i 是 num 的因数，那么 num/i 也是。

因此，如果素因子高于平方根，您可以使用 same 循环提前退出(因为这些是按降序顺序找到的，找到的第一个是最高的)。

否则继续前进，直到您达到平方根并获得迄今为止找到的最高值(在这种情况下您需要最后一个，因为您正在按升序搜索)。

代码如下:

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

它在 一秒钟内返回结果 333667:

pax$ time ruby testprog.rb
333667

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

这比您最初的 55 秒解决方案快了大约 350 倍，希望这对您来说足够快:-)

甚至更快，如果您通过以下方式去除流程启动/关闭成本:

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

给出:

    user     system      total        real
0.000000   0.000000   0.000000 (  0.000316)