c++ - 在 C++ 中使用 AKS 素数测试计算双素数我做错了什么？

Question

晚安，我不是 C++ 专家。我需要计算 3 内孪生素数的数量和极限。我的输出总是给出 1。我做错了什么？这是我的 AKS 算法也能正常工作!

#include <bits/stdc++.h>
using namespace std;

long long c[100];

void coef(int n)
{
    c[0] = 1;
    for (int i = 0; i < n; c[0] = -c[0], i++) {
        c[1 + i] = 1;

        for (int j = i; j > 0; j--)
            c[j] = c[j - 1] - c[j];
    }
}

bool isPrime(int n)
{

    coef(n);


    c[0]++, c[n]--;


    int i = n;
    while (i-- && c[i] % n == 0)
        ;


    return i < 0;
}

int main()
{
    int limit=10000,counter=1,i;
    for(i=3;i<=limit;i+=2){
    if (isPrime(i)){

        if(isPrime(i+2)){
                counter++;
    }
 }
}
cout <<counter;
return 0;
}

我在 Windows 10 专业版上使用 codeblocks 17.02。我在做什么傻事？

Answer 1

这根本不是用于素数的 AKS 算法。它看起来像是 RosettaCode task 的略微修改版本它实现了指数时间引理。它会比简单的试验除法慢，更不用说如果没有模块化算法，这个实现基本上是无用的，因为即使是玩具大小的输入也会溢出。

一旦您进行了适当的素数测试，需要考虑的一件事就是不要对相同的输入一遍又一遍地调用 isprime()。您可以为每个数字调用一次，只记住您找到的最后一个素数。如果 isprime(i) 为真，则计算您找到的最后一个是否为 i-2。现在您不需要重复调​​用，也不需要值数组。

更好的是，因为您想生成 n 的所有素数，所以可以使用筛子。对于该任务，它比素数测试更有效，即使使用更好的素数测试也是如此。您可以在 RosettaCode page for that task 找到简单的 C 版本.那里有更好的，但考虑到您的起点，这在这里并不重要。