改进算法执行时间和素数

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() 调用中的 "trick" - 如果 i 是 num 的因数，那么 num / i.

也是

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

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

此代码类似于：

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

其中returns结果333667在好秒下：

pax$ time ruby testprog.rb
333667

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

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

甚至更快如果你去掉这个过程 startup/shutdown 成本为：

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)

改进算法执行时间和素数

Improving algorithm execution time and prime numbers

ruby

algorithm

primes