对小数的最快素数测试

我在业余时间玩了 Euler 项目，现在我需要做一些重构。我已经实施了 Miller-Rabin 以及一些筛子。我以前听说过，对于较小的数量（例如数百万以下），筛子实际上更快。有人有这方面的信息吗？谷歌并没有多大帮助。

Yes, you'll find with most algorithms that you can trade space for time. In other words, by allowing the use of more memory, the speed is greatly increased ^*a.

我其实不knowMiller-Rabin 算法，但是，除非它比单个左移/添加和内存提取更简单，否则它将被预先计算的筛子从水中吹出。

这里重要的是预先计算的。就性能而言，预先计算这样的事情是个好主意，因为前一百万个素数在不久的将来不太可能改变:-)

换句话说，用类似的东西创建你的筛子：

unsigned char primeTbl[] = {0,0,1,1,0,1,0,1,0,0,0,1};
#define isPrime(x) ((x < sizeof(primeTbl) ? primeTbl[x] : isPrimeFn(x))

所有关于不要传递诸如此类的常见警告a++进入宏。这为您提供了两全其美的功能，即对“小”素数进行极其快速的表查找，对于范围之外的素数则返回到计算方法。

显然，您将使用其他方法之一编写一个程序来生成该查找表 - 您真的不想手动输入所有内容。

但是，与所有优化问题一样，测量，不要猜测！

^*a A classic case of this was some trig functions I once had to write for an embedded system. This was a competitive contract bid and the system had a little more storage than CPU grunt.

我们实际上赢得了合同，因为我们的功能基准数据击败了竞争对手。

为什么？因为我们预先将这些值计算到最初在另一台机器上计算的查找表中。通过明智地使用归约（将输入值降低到 90 度以下）和三角属性（余弦只是正弦的相移，并且其他三个象限与第一个象限相关），我们将查找表简化为180 个条目（每半度一个）。

最好的解决方案是那些优雅的and狡猾的:-)

不管怎样，下面的 C 代码将为您生成这样一个表，其中包含 400 万以下的所有素数（其中 283,000 个）。

#include <stdio.h>

static unsigned char primeTbl[4000000];

int main (void) {
    int i, j;

    for (i = 0; i < sizeof(primeTbl); i++)
        primeTbl[i] = 1;

    primeTbl[0] = 0;
    primeTbl[1] = 0;
    for (i = 2; i < sizeof(primeTbl); i++)
        if (primeTbl[i])
            for (j = i + i; j < sizeof(primeTbl); j += i)
                primeTbl[j] = 0;

    printf ("static unsigned char primeTbl[] = {");
    for (i = 0; i < sizeof(primeTbl); i++) {
        if ((i % 50) == 0) {
            printf ("\n   ");
        }
        printf ("%d,", primeTbl[i]);
    }
    printf ("\n};\n");
    printf ("#define isPrime(x) "
        "((x < sizeof(primeTbl) ? primeTbl[x] : isPrimeFn(x))\n");

    return 0;
}

如果你能提高primeTbl如果将表添加到 1600 万个条目 (16M)，您会发现这足以将素数计数保持在 100 万以上（前 1,031,130 个素数）。

现在有一些方法可以减少存储空间，例如仅存储奇数并调整宏来解决这个问题，或者使用位掩码而不是无符号字符。如果内存可用的话，我自己更喜欢算法的简单性。