小数的最快素数检验

是的,你会发现大多数算法可以用空间来换取时间。换句话说,通过允许使用更多内存,速度大大提高

知道 米勒-拉宾算法,但除非它比一次左移/加法和内存提取简单,否则它将被预先计算好的筛子吹出水面。

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

换言之,使用以下内容创建筛子:

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

我们实际上赢得了这份合同,因为我们的功能基准数字把竞争搞砸了。

为什么?因为我们将这些值预先计算到另一台机器上最初计算的查找表中。通过明智地使用缩减(将输入值降到90度以下)和触发器属性(余弦只是正弦的相移,其他三个象限与第一个象限相关),我们将查找表降到180个条目(每半度一个条目)。

和 狡猾的:-)

值得一提的是,下面的C代码将为您生成这样一个表,所有低于400万(其中283000个)的素数。

#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万以上(前1031130个素数)。

现在有一些方法可以减少存储量,比如只存储奇数并调整宏来处理,或者使用位掩码而不是无符号字符。如果内存可用,我更喜欢算法的简单性。

我建议采用分层方法。首先,确保没有小的首要因素。试着用前20或30个素数除法是可行的,但是如果你使用一个聪明的方法,你可以减少使用gcd所需要的除数。这个步骤过滤掉了大约90%的复合材料。

最后的证明步骤取决于你想走多大。如果你愿意在一个小范围内工作,在一个2-伪素数的列表上做一个二进制搜索,直到你允许的最大值为止。如果是2^32,那么您的列表将只有10403个成员,因此查找应该只需要14个查询。

如果你想升到2^64,现在就足够了(多亏了 Jan Feitisma )检查数字是否为BPSW伪素数。(您还可以下载所有异常的3gb列表,删除trial division将删除的异常,并编写基于磁盘的二进制搜索。) T. R. Nicely 有一个很好的页面解释如何合理有效地实现这一点。

作为预计算概念的变体,您可以首先廉价地检查候选数字 p 第 ^p-1级 =1(模式p)。这将在某个时候失败,但它的工作高达1亿,因为我测试了它(预计算)。

编辑:

如果候选人 第 可以被2,3,5,7,或11整除,声明它是复合的;
否则如果 第 是{4181921、4469471、5256091、9006401、9863461}之一,声明它是复合的;
否则如果
否则声明为复合。

编辑2:

嗯,看来我想要的信息已经在维基百科上了 Miller-Rabin algorithm ,标题为 "Deterministic variants of the test"

唯一的办法就是给自己做个基准。当你这样做的时候,把它写下来,然后放到网上的某个地方。