如何找到更聪明的算法来检查成对的素数以查看它们是否配对产生另一个素数？

Question

我卡在 Project Euler question 60 上了。我知道建议不要太问问题或在网上找到有关它的答案，否则我找不到继续下去的动力。所以我希望能在这里找到一些帮助，让我继续前进。

免责声明再见，我的问题本质上是程序性的。问题是

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.

现在我的想法是使用天真的方法，只找到所有五个素数的集合，直到某个 nth 素数（在问题中给出的是 673 是要达到的最高值用这个属性找到四个素数，所以我决定先找到第 800 个素数），然后找到所有可能的对，然后检查我们是否能找到一个所有可能的对都不是素数的对：

require 'prime'

def concat a, b

  val_arr = (a.to_s + b.to_s).scan(/\d/).map { |s| s.to_i }
  retval = 0
  factor = 1

  until val_arr.empty? 
    retval += val_arr.pop * factor
    factor *= 10
  end

  retval

end

primes = Prime.take(800) # Arbitrary large, but not too large, value

prime_sets = p primes.combination(5).to_a
prime_duos = primes.permutation(2).to_a # <= takes too long

prime_sets.each do |set| 
  puts set.reduce(:+) if set.permutation(2).all? { |duo| (concat duo.first, duo.last).prime? }
end

prime_duos 方法似乎永远不会停止。即使使用较低的值（最多 100 个素数）也需要很长时间。

我怎样才能做出更聪明的算法？

Answer 1

我不认为排列是你的问题。在我的电脑上，这些执行时间不到 1/10 秒。

现在，组合，OTOH，这是一个不同的问题。我的意思是，忘记计算需要多长时间。看看有多少：800 重复选择 5，即 2764949600160 排列。即使你有 5GHz CPU，并且可以在每个时钟周期计算一个排列，它仍然需要 9 分 12 秒来计算。

在 32 位系统上，Ruby Fixnum 占用 4 个字节，在 64 位系统上，它是 8 个字节。您存储这些排列的 Array 需要超过10 TB RAM（64 位系统上为 20 TB）。

另外，您正在打印所有这些数字。控制台慢。真的 S-L-O-W。我想你可能每毫秒打印不超过一行。这将花费你大约 88 年的时间来打印。

因此，总而言之：您正在使用可能需要小时才能完成的计算，将结果存储在 20 TB 数组中，然后打印出来……然后您在您的实际算法甚至开始之前完成所有这些。

Answer 2

你的效率问题是你试图通过构建一个非常大的可能性集并按结果过滤来找到目标素数。所有构建块及其组合的集合比可用目标大得多，因此您花费大量时间构建组合，结果几乎过滤掉了所有这些。

从一组可能的目标 "combined" 素数开始工作更有意义。你知道这些目标数字必须分解成两个更小的素数。基于此的策略将松散地工作如下：

生成不超过某个目标数的素数列表 - 一百万（或者可能是一千万）。这可以很快完成，例如Prime.take(75000)
使用该列表生成允许对的拆分（与连接相反）数组。从 Prime.take(75000) 开始，有 23494 个这样的对，有 7216 个独特的素数，并且可以在几秒钟内生成该列表 - 与您在原始代码中尝试处理的项目数量形成对比。
显然不要拿那个 7216 个素数的列表直接使用它，你会回到你开始的地方。相反，使用您生成的对列表来创建一个有效的搜索一组 5 满足您的约束。想一想这样一组 5 人的属性，您可以使用有效对列表进行测试。

我希望这足以让您重新开始。我不会提供此解决方案的其余部分或任何 Ruby 代码，因为我认为它会降低欧拉挑战的价值。

如何找到更聪明的算法来检查成对的素数以查看它们是否配对产生另一个素数？

How to find more clever algorithm to check pairs of primes to see if paired they produce another prime?

ruby

algorithm

primes

mathematical-optimization