改进算法执行时间和素数

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也是。

因此，如果质因子在平方根以上，您可以使用相同的循环提前退出（因为这些因子是按降序找到的，所以找到的第一个是最高的）。

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

这方面的代码应该是这样的：

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

其在第二下返回井中的结果CCD_ 5

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)

Answer 2

怎么样：

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)