找出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;
}

正如您所看到的,我必须计算min和max之间的每个数字可以表示为两个素数之和的次数.

primes是一个ArrayList,所有素数在2 到2000000之间.在这种情况下,min是1000000并且max是2000000,这就是素数到2000000的原因.

我的方法很好,但这里的目标是更快地做点什么.

我的方法需要两个循环,一个在另一个内部,它使我的算法成为O(n²).它像泡泡一样糟透了.

如何重写我的代码以获得更好的复杂性,如O(nlogn)？

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

Answer 1

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

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

其中，prime(x)如果 x 是素数，则 1，否则为 0。我们不计算两个素数相加为 的方式的数量x，而是考虑两个非负整数相加为 的所有方式x，如果这两个整数是素数，则在总和上加 1。

这并不是一种更有效的计算方法。然而，将其置于这种形式可以帮助我们认识到我们想要的输出是两个序列的离散卷积。具体来说，如果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元素序列，基于快速傅立叶变换O(n*log(n))的算法可以按时间而不是按时间计算卷积O(n**2)。不幸的是，我的解释到此结束。即使您有适当的数学符号，快速傅里叶变换也很难解释，并且由于我对 Cooley-Tukey 算法的记忆并不像我希望的那么精确，所以我无法真正做到公正。

如果您想了解有关卷积和傅里叶变换的更多信息，特别是Cooley-Tukey FFT 算法，我刚刚链接的维基百科文章将是一个不错的开始。如果您只是想使用更快的算法，那么最好的选择是获得一个可以执行此操作的库。在 Python 中，我知道scipy.signal.fftconvolve可以完成这项工作；在其他语言中，您可能可以通过您选择的搜索引擎很快找到一个库。