java - 求 N 和 M 之间的每个数字可以表示为一对素数之和的次数

Question

考虑这个方法:

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 是一个包含 2 到 2000000 之间所有素数的 ArrayList。在这种情况下，min 是 1000000，max 是 2000000，这就是为什么素数一直到 2000000。

我的方法工作正常，但这里的目标是更快地完成某些事情。

我的方法采用两个循环，一个在另一个循环中，它使我的算法成为 O(n²)。它像冒泡排序一样糟糕。

我怎样才能重写我的代码，以更复杂的方式完成相同的结果，例如 O(nlogn)？

最后一件事:我正在用 Java 编写代码，但您的回复也可以使用 Python、VB.Net、C#、Ruby、C 甚至只是英文解释。

Answer 1

对于 min 和 max 之间的每个数字 x，我们要计算 x 可以通过的方式的数量写成两个素数之和。这个数字也可以表示为

sum(prime(n)*prime(x-n) for n in xrange(x+1))

如果 x 是素数，则 prime(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 -based 算法可以在 O(n*log(n)) 时间内计算卷积，而不是 O(n**2) 时间。不幸的是，我的解释到此结束。快速傅里叶变换有点难以解释，即使你有适当的数学符号可用，而且我对 Cooley-Tukey 算法的内存并不像我希望的那样精确，我不能真正做到公正.

如果您想了解更多关于 convolution 的信息和 Fourier transforms ，特别是 Cooley-Tukey FFT algorithm ，我刚刚链接的维基百科文章将是一个不错的开始。如果您只想使用更快的算法，最好的办法是获得一个可以执行此操作的库。在 Python 中，我知道 scipy.signal.fftconvolve会做这份工作；在其他语言中，您可能可以通过您选择的搜索引擎很快找到一个图书馆。