求 N 和 M 之间的每个数字可以表示为一对素数之和的次数
Find how many times each number between N and M can be expressed as a sum of a pair of primes
考虑这个方法：
public static int[] countPairs(int min, int max) {
int lastIndex = primes.size() - 1;
int i = 0;
int howManyPairs[] = new int[(max-min)+1];
for(int outer : primes) {
for(int inner : primes.subList(i, lastIndex)) {
int sum = outer + inner;
if(sum > max)
break;
if(sum >= min && sum <= max)
howManyPairs[sum - min]++;
}
i++;
}
return howManyPairs;
}
如你所见，我必须计算最小值和最大值之间的每个数字可以表示为两个素数之和的次数。
primes 是一个 ArrayList，所有素数都在 2 到 2000000 之间。在这种情况下，min 是 1000000，max 是 2000000，这就是素数一直到 2000000 的原因。
我的方法工作正常，但这里的目标是更快地完成某些事情。
我的方法采用两个循环，一个在另一个循环中，这使我的算法成为 O(n²)。它像冒泡排序一样糟糕。
我如何重写我的代码，以更复杂的方式完成相同的结果，例如 O(nlogn)？
最后一件事：我正在使用 Java 编写代码，但您的回复也可以使用 Python、VB.Net、C#、Ruby、C 甚至只是英文解释。
两个质数之和表示N = A + B，其中A和B是质数，A < B表示A < N / 2和B > N / 2.请注意，它们不能等于 N / 2.
因此，您的外循环应该只从 1 循环到 floor((N - 1) / 2)。在整数数学中，floor 是自动的。
如果质数存储在 Set 中，则可以消除您的内部循环。假设您的数组已排序（公平假设），请使用 LinkedHashSet，以便在外循环中迭代集合可以在 (N - 1) / 2.
处停止
我会留给你编码。
更新
抱歉，以上是针对特定 N 查找 A 和 B 问题的答案。您的问题是找到 min 和 max（含）之间的所有 N。
如果您遵循上述逻辑，您应该能够将其应用到您的问题中。
外循环应该是从 1 到 max / 2。
内循环应该是从 min - outer 到 max - outer.
要找到内循环的起点，您可以在周围保留一些额外的索引变量，或者您可以依靠正在排序的素数数组并使用Arrays.binarySearch(primes, min - outer)。第一个选项可能会快一点，但第二个选项肯定更简单。
您要搜索的是每个数字 Goldbach partitions 的计数
在你的范围内，恕我直言，没有有效的算法。
不偶数有0，4*10^18以下的偶数保证有0以上，
但除此之外...首先，如果存在具有 0 个分区的偶数（大于 4*10^18）
是1700年以来的未解之题，精确数字之类的问题就更复杂了。
有一些渐近和启发式的解决方案，但如果你想要确切的数字，
除了获得更多 CPU 和 RAM，您无能为力。
对于 min 和 max 之间的每个数字 x，我们要计算 x 可以写成两个素数之和的方式的数量。这个数字也可以表示为
sum(prime(n)*prime(x-n) for n in xrange(x+1))
其中 prime(x) 如果 x 是素数则为 1，否则为 0。我们不计算两个素数加起来等于 x 的方式的数量，而是考虑两个非负整数加起来等于 x 的所有方式，如果两个整数是素数，则在总和上加 1。
这不是一种更有效的计算方式。但是，将其置于这种形式有助于我们认识到我们想要的输出是两个序列的 discrete convolution。具体来说，如果 p 是满足 p[x] == prime(x) 的无限序列，那么 p 与自身的卷积就是满足
的序列
convolve(p, p)[x] == sum(p[n]*p[x-n] for n in xrange(x+1))
或者，替换 p、
的定义
convolve(p, p)[x] == sum(prime(n)*prime(x-n) for n in xrange(x+1))
换句话说，将 p 与自身进行卷积产生我们要计算的数字序列。
计算卷积的直接方法与您所做的差不多，但还有更快的方法。对于 n 元素序列，基于 fast Fourier transform 的算法可以在 O(n*log(n)) 时间内而不是 O(n**2) 时间内计算卷积。不幸的是，我的解释到此结束。快速傅里叶变换有点难以解释，即使你有适当的数学符号可用，而且由于我对 Cooley-Tukey 算法的记忆并不像我希望的那样精确，我不能真正做到公正.
如果您想阅读更多有关 convolution and Fourier transforms, particularly the Cooley-Tukey FFT algorithm, the Wikipedia articles I've just linked would be a decent start. If you just want to use a faster algorithm, your best bet would be to get a library that does it. In Python, I know scipy.signal.fftconvolve 的内容，就可以了；在其他语言中，您可能可以通过您选择的搜索引擎很快找到一个图书馆。
其他答案有一个从 N 到 M 的外循环。但是，外循环（或多个循环）是质数对，用于构建 N 和 M 之间的数字列表更有效等于他们的总和。
因为我不知道Java我会在Ruby中给出一个具体例子的解决方案。这应该允许任何有兴趣在 Java 中实现算法的人，无论他们是否知道 Ruby.
我最初假设乘积等于 M 和 N 之间的数字的两个素数必须是唯一的。也就是说，4 不能表示为 4 = 2+2.
使用Ruby的质数库。
require 'prime'
假设 M 和 N 分别为 5 和 50。
lower = 5
upper = 50
计算直到 upper-2 #=> 48 的质数，2 是第一个质数。
primes = Prime.each.take_while { |p| p < upper-2 }
#=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
构建两个素数的所有组合的枚举数。
enum = primes.combination(2)
=> #<Enumerator: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]:combination(2)>
我们可以通过将此枚举器转换为数组来查看将生成的元素。
enum.to_a
#=> [[2, 3], [2, 5],..., [2, 47], [3, 5],..., [43, 47]] (105 elements)
只要把enum想象成一个数组。
现在构造一个计数散列，其键为 lower 和 upper 之间的数字，其中至少有一对素数总和等于该数字，其值是求和为关联键值的素数。
enum.each_with_object(Hash.new(0)) do |(x,y),h|
sum = x+y
h[sum] += 1 if (lower..upper).cover?(sum)
end
#=> {5=>1, 7=>1, 9=>1, 13=>1, 15=>1, 19=>1, 21=>1, 25=>1, 31=>1, 33=>1,
# 39=>1, 43=>1, 45=>1, 49=>1, 8=>1, 10=>1, 14=>1, 16=>2, 20=>2, 22=>2,
# 26=>2, 32=>2, 34=>3, 40=>3, 44=>3, 46=>3, 50=>4, 12=>1, 18=>2, 24=>3,
# 28=>2, 36=>4, 42=>4, 48=>5, 30=>3, 38=>1}
例如，这表明 16 有两种方式可以表示为两个质数之和（3+13 和 5+11），三种方式表示 34 (3+31, 5+29 和 11+23) 而 6.
没办法
如果求和的两个素数不需要是唯一的（例如，要包括 4=2+2），则只需要稍作改动。
arr = primes.combination(2).to_a.concat(primes.zip(primes))
其排序值是
a = arr.sort
#=> [[2, 2], [2, 3], [2, 5], [2, 7],..., [3, 3],..., [5, 5],.., [47, 47]] (120 elements)
然后
a.each_with_object(Hash.new(0)) do |(x,y),h|
sum = x+y
h[sum] += 1 if (lower..upper).cover?(sum)
end
#=> {5=>1, 7=>1, 9=>1, 13=>1, 15=>1, 19=>1, 21=>1, 25=>1, 31=>1, 33=>1,
# 39=>1, 43=>1, 45=>1, 49=>1, 6=>1, 8=>1, 10=>2, 14=>2, 16=>2, 20=>2,
# 22=>3, 26=>3, 32=>2, 34=>4, 40=>3, 44=>3, 46=>4, 50=>4, 12=>1, 18=>2,
# 24=>3, 28=>2, 36=>4, 42=>4, 48=>5, 30=>3, 38=>2}
a 应替换为 arr。我在这里使用 a 只是为了对结果散列的元素进行排序，以便于阅读。
由于我只是想描述这个方法，所以我使用了暴力法来枚举primes的元素对，丢弃了120对素数中的44对，因为它们的总和超出了范围5..50（a.count { |x,y| !(lower..upper).cover?(x+y) } #=> 44）。显然，还有很大的改进空间。
考虑这个方法：
public static int[] countPairs(int min, int max) {
int lastIndex = primes.size() - 1;
int i = 0;
int howManyPairs[] = new int[(max-min)+1];
for(int outer : primes) {
for(int inner : primes.subList(i, lastIndex)) {
int sum = outer + inner;
if(sum > max)
break;
if(sum >= min && sum <= max)
howManyPairs[sum - min]++;
}
i++;
}
return howManyPairs;
}
如你所见，我必须计算最小值和最大值之间的每个数字可以表示为两个素数之和的次数。
primes 是一个 ArrayList，所有素数都在 2 到 2000000 之间。在这种情况下，min 是 1000000，max 是 2000000，这就是素数一直到 2000000 的原因。
我的方法工作正常，但这里的目标是更快地完成某些事情。
我的方法采用两个循环，一个在另一个循环中，这使我的算法成为 O(n²)。它像冒泡排序一样糟糕。
我如何重写我的代码，以更复杂的方式完成相同的结果，例如 O(nlogn)？
最后一件事：我正在使用 Java 编写代码，但您的回复也可以使用 Python、VB.Net、C#、Ruby、C 甚至只是英文解释。
两个质数之和表示N = A + B，其中A和B是质数，A < B表示A < N / 2和B > N / 2.请注意，它们不能等于 N / 2.
因此，您的外循环应该只从 1 循环到 floor((N - 1) / 2)。在整数数学中，floor 是自动的。
如果质数存储在 Set 中，则可以消除您的内部循环。假设您的数组已排序（公平假设），请使用 LinkedHashSet，以便在外循环中迭代集合可以在 (N - 1) / 2.
我会留给你编码。
更新
抱歉，以上是针对特定 N 查找 A 和 B 问题的答案。您的问题是找到 min 和 max（含）之间的所有 N。
如果您遵循上述逻辑，您应该能够将其应用到您的问题中。
外循环应该是从 1 到 max / 2。
内循环应该是从 min - outer 到 max - outer.
要找到内循环的起点，您可以在周围保留一些额外的索引变量，或者您可以依靠正在排序的素数数组并使用Arrays.binarySearch(primes, min - outer)。第一个选项可能会快一点，但第二个选项肯定更简单。
您要搜索的是每个数字 Goldbach partitions 的计数
在你的范围内，恕我直言，没有有效的算法。
不偶数有0，4*10^18以下的偶数保证有0以上，
但除此之外...首先，如果存在具有 0 个分区的偶数（大于 4*10^18）
是1700年以来的未解之题，精确数字之类的问题就更复杂了。
有一些渐近和启发式的解决方案，但如果你想要确切的数字，
除了获得更多 CPU 和 RAM，您无能为力。
对于 min 和 max 之间的每个数字 x，我们要计算 x 可以写成两个素数之和的方式的数量。这个数字也可以表示为
sum(prime(n)*prime(x-n) for n in xrange(x+1))
其中 prime(x) 如果 x 是素数则为 1，否则为 0。我们不计算两个素数加起来等于 x 的方式的数量，而是考虑两个非负整数加起来等于 x 的所有方式，如果两个整数是素数，则在总和上加 1。
这不是一种更有效的计算方式。但是，将其置于这种形式有助于我们认识到我们想要的输出是两个序列的 discrete convolution。具体来说，如果 p 是满足 p[x] == prime(x) 的无限序列，那么 p 与自身的卷积就是满足
convolve(p, p)[x] == sum(p[n]*p[x-n] for n in xrange(x+1))
或者，替换 p、
convolve(p, p)[x] == sum(prime(n)*prime(x-n) for n in xrange(x+1))
换句话说，将 p 与自身进行卷积产生我们要计算的数字序列。
计算卷积的直接方法与您所做的差不多，但还有更快的方法。对于 n 元素序列，基于 fast Fourier transform 的算法可以在 O(n*log(n)) 时间内而不是 O(n**2) 时间内计算卷积。不幸的是，我的解释到此结束。快速傅里叶变换有点难以解释，即使你有适当的数学符号可用，而且由于我对 Cooley-Tukey 算法的记忆并不像我希望的那样精确，我不能真正做到公正.
如果您想阅读更多有关 convolution and Fourier transforms, particularly the Cooley-Tukey FFT algorithm, the Wikipedia articles I've just linked would be a decent start. If you just want to use a faster algorithm, your best bet would be to get a library that does it. In Python, I know scipy.signal.fftconvolve 的内容，就可以了；在其他语言中，您可能可以通过您选择的搜索引擎很快找到一个图书馆。
其他答案有一个从 N 到 M 的外循环。但是，外循环（或多个循环）是质数对，用于构建 N 和 M 之间的数字列表更有效等于他们的总和。
因为我不知道Java我会在Ruby中给出一个具体例子的解决方案。这应该允许任何有兴趣在 Java 中实现算法的人，无论他们是否知道 Ruby.
我最初假设乘积等于 M 和 N 之间的数字的两个素数必须是唯一的。也就是说，4 不能表示为 4 = 2+2.
使用Ruby的质数库。
require 'prime'
假设 M 和 N 分别为 5 和 50。
lower = 5
upper = 50
计算直到 upper-2 #=> 48 的质数，2 是第一个质数。
primes = Prime.each.take_while { |p| p < upper-2 }
#=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
构建两个素数的所有组合的枚举数。
enum = primes.combination(2)
=> #<Enumerator: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]:combination(2)>
我们可以通过将此枚举器转换为数组来查看将生成的元素。
enum.to_a
#=> [[2, 3], [2, 5],..., [2, 47], [3, 5],..., [43, 47]] (105 elements)
只要把enum想象成一个数组。
现在构造一个计数散列，其键为 lower 和 upper 之间的数字，其中至少有一对素数总和等于该数字，其值是求和为关联键值的素数。
enum.each_with_object(Hash.new(0)) do |(x,y),h|
sum = x+y
h[sum] += 1 if (lower..upper).cover?(sum)
end
#=> {5=>1, 7=>1, 9=>1, 13=>1, 15=>1, 19=>1, 21=>1, 25=>1, 31=>1, 33=>1,
# 39=>1, 43=>1, 45=>1, 49=>1, 8=>1, 10=>1, 14=>1, 16=>2, 20=>2, 22=>2,
# 26=>2, 32=>2, 34=>3, 40=>3, 44=>3, 46=>3, 50=>4, 12=>1, 18=>2, 24=>3,
# 28=>2, 36=>4, 42=>4, 48=>5, 30=>3, 38=>1}
例如，这表明 16 有两种方式可以表示为两个质数之和（3+13 和 5+11），三种方式表示 34 (3+31, 5+29 和 11+23) 而 6.
如果求和的两个素数不需要是唯一的（例如，要包括 4=2+2），则只需要稍作改动。
arr = primes.combination(2).to_a.concat(primes.zip(primes))
其排序值是
a = arr.sort
#=> [[2, 2], [2, 3], [2, 5], [2, 7],..., [3, 3],..., [5, 5],.., [47, 47]] (120 elements)
然后
a.each_with_object(Hash.new(0)) do |(x,y),h|
sum = x+y
h[sum] += 1 if (lower..upper).cover?(sum)
end
#=> {5=>1, 7=>1, 9=>1, 13=>1, 15=>1, 19=>1, 21=>1, 25=>1, 31=>1, 33=>1,
# 39=>1, 43=>1, 45=>1, 49=>1, 6=>1, 8=>1, 10=>2, 14=>2, 16=>2, 20=>2,
# 22=>3, 26=>3, 32=>2, 34=>4, 40=>3, 44=>3, 46=>4, 50=>4, 12=>1, 18=>2,
# 24=>3, 28=>2, 36=>4, 42=>4, 48=>5, 30=>3, 38=>2}
a 应替换为 arr。我在这里使用 a 只是为了对结果散列的元素进行排序，以便于阅读。
由于我只是想描述这个方法，所以我使用了暴力法来枚举primes的元素对，丢弃了120对素数中的44对，因为它们的总和超出了范围5..50（a.count { |x,y| !(lower..upper).cover?(x+y) } #=> 44）。显然，还有很大的改进空间。